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>usingnamespacestd; intmain(void){intN; intt = 0; inta[100][100]; intpr[100]; intS = 1<<31, s = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j; cin >> N; for(inti = 0; i < N; i++)for(j = 0; j < N; j++)cin >> a[i][j]; for(intz = 0; z < N; z++){for(inti = 0; i < N; i++)pr[i] = 0; for(intx = z; x < N; x++){t = 0; s = 1<<31; j = 0; k = 0; l = 0; for(inti = 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; return0; }
Algorithm by prefix sum
k-maximum Subarray problem
page revision: 5, last edited: 16 Nov 2006 20:44