Maximum interval sum

Or maximum contiguous subvector of the input.

Do a linear sweep from left to right, accumulate the sum. Start new interval whenever you encounter partial sum < 0.

/* 1-d linear alg O(n) */
inline int mis1d(int line[], int size) {
    int maxv = -INF;
    int p = 0;
    for(int i = 0; i < size; ++i) {
        p += line[i];
        if(p < 0) p = 0;
        if(p > maxv) maxv = p;
    }
    return maxv;
}

In a 2D problem, we are expected to find a maximum sum subrectangle in a mxn matrix. 

• We first calculate the accumulative sum in the dimension of length m (smaller dim).


• We then use the above technique in the dimension of length n.


• The total running time is O(m^2 n). (for nxn matrix, that is O(n^3) )

UVa problem: 108, 836

#include <iostream>
using namespace std;

#define INF 999999999
int M[101][101];
int partialSum[101][101];
int line[101];

/* 1-d linear alg O(n) */
inline int mis1d(int line[], int size) {
    int maxv = -INF;
    int p = 0;
    for(int i = 0; i < size; ++i) {
        p += line[i];
        if(p < 0) p = 0;
        if(p > maxv) maxv = p;
    }
    return maxv;
}

/* 2-D O(n^3) */
int mis2d(int size) {
    int maxv = -INF;
    for(int j = 0; j < size; ++j) {
        partialSum[0][j] = M[0][j];
        for (int i = 1; i < size; i++)
            partialSum[i][j] = partialSum[i-1][j] + M[i][j];
    }
    for(int i = 0; i < size; ++i) {   // use from the i-th row
        for(int j = i; j < size; ++j) {  // to the j-th row
            if(i == j) 
                memcpy(line, M[i], size*sizeof(int));
            else {
                // generate the data i to j-th row
                for(int k = 0; k < size; ++k)
                    line[k] = partialSum[j][k] - partialSum[i][k];
            }
            int v = mis1d(line, size);
            if(v > maxv) maxv = v;
        }
    }
    return maxv;
}

int main() {
    int n;
    while(scanf("%d ", &n) == 1) {
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                scanf("%d", &M[i][j]);
        printf("%d\n", mis2d(n));
    }
}

Related problems:

• find the subvector with the sum closest to zeros




• calc the accumulative sum so that cum[i] = x[0] + ... + x[i]


• The subvector x[l ... u] sums to zeros if cum[l-1] = cum[u]


• the subvector with the sum closest to zeros is found by locating the two closest elements in cum


• which can be done in O(nlogn) by sorting


• find the subvector with the sum closest to a given real number t.




• a simple extension from the above case


• The subvector x[l ... u] sums to t if cum[l-1] + t = cum[u] and l-1<u


• first nlogn sorting


• then for each element, do a (log n) binary search for closest to (cum[i]+t)