清华大学出版社 动态规划算法 记b=m1≤j≤n,则所求的最大子段和为 mx∑q=mxmx∑]=mxb 当b1>0时b=b-1+a,否则b=a。由此可得计算b的 动态规划递归式 b]=maxb-1+a],a},1≤j≤n public static int maxSumO int n=a length-1 int sum=0 b=0 for(int i=1; i<=n; i++) if (>0)+=a] else b=a0 if (b>sum)sum=b return sum|算法显然需要O()计算时间和o()空间6 动态规划算法 记 ，1 j n，则所求的最大子段和为 当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得计算b[j]的 动态规划递归式 [ ] max{ [ ]} 1 =   = j k i i j b j a k max [ ] max max [ ] max [ ] 1 1 1 1 a k a k b j j n j k i j n i j j k i i j n   =     =     =  = b[j]=max{b[j-1]+a[j]，a[j]}， 1 j n 算法显然需要O(n)计算时间和O(n)空间。 public static int maxSum() { int n=a.length-1; int sum=0, b=0; for (int i=1;i<=n;i++) { if (b>0) b+=a[i]; else b=a[i]; if (b>sum)sum=b; } return sum; }