連續子數組的最大和

02-26

連續子數組的最大和

輸入一個數組，數組裡有正數，負數。數組中有一個或多個連續的整數組成一個子數組，求子數組的最大值。

思路：

動態規劃，定義函數f(i)表示以第i個數字結尾的子數組的最大和，那麼我們需要求出max[f(i)]，其中0 <= i < n。遞推公式：

f(i) = pdata[i] i=0 or f(i-1)<0 f(i) = f(i-1)+pdata[i] i>0 and f(i-1)>0

參考代碼：

root@gt:/home/git/Code# ./a.out 18root@gt:/home/git/Code# cat maxdp.c #include <stdio.h>int dp(int* pdata,int len){ if(pdata == NULL || len <= 0) return 0; int f = pdata[0]; int max = 0; for(int i = 1;i < len;++i) { if(f <= 0) { f = pdata[i]; max = 0; } else { if(max < f) max = f; f += pdata[i]; } } return max;}int main(){ int pdata[] = {1,-2,3,10,-4,7,2,-5}; int res = dp(pdata,sizeof(&pdata)); printf("%d ",res); return 0;}