Maximum subarray sum problem
Kadane's 1D algorithm O(N)
Kadane's algorithm /* maximum subarray a[k..l] of a[1..n] */
(k; l) := (0; 0); s := -inf; t := 0; j := 1;
for i:=1 to n do begin
t := t + a[i];
if t > s then begin (k; l) := (j; i); s := t end;
if t < 0 then begin t := 0; j := i + 1 end
end
Kadane's 2D algorithm O(N3)
#include <iostream> #include <algorithm> using namespace std; int main( void ) { int N; int t = 0; int a[100][100]; int pr[100]; int S = 1<<31, s = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j; cin >> N; for( int i = 0; i < N; i++) for( j = 0; j < N; j++) cin >> a[i][j]; for( int z = 0; z < N; z++) { for(int i = 0; i < N; i++) pr[i] = 0; for(int x = z; x < N; x++) { t = 0; s = 1<<31; j = 0; k = 0; l = 0; for(int i = 0; i < N; i++) { pr[i] = pr[i] + a[x][i]; t = t + pr[i]; if( t > s) { s = t; k = i; l = j; } if( t < 0 ) { t = 0; j = i + 1; } } if( s > S) { S = s; x1 = x; y1 = k; x2 = z; y2 = l; } } } cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl; cout << S; return 0; }
Algorithm by prefix sum
k-maximum Subarray problem
page revision: 5, last edited: 16 Nov 2006 20:44