动态规划之最大子段和问题
问题描述
有一个由呢个整数组成的数列A={a1，a2，......，an}，截取其中从i - j开始的子段并计算字段和，求最大的字段和为多少？
例如A={1,3,-5,3,-2,5,-4,3}
则其最大字段和为3+（-2）+5 =6
使用动态规划算法求解问题
假设最大子段和设为M
设从1到j中包括a[j]的最大子段和为b[j]
所以有：
b[j] = max{b[j-1]+a[j]，a[j]}
M = max{b[j]} ( 1=<j<=n)
代码求解
public class MaxSum {
public static void maxSum(int[]arr){
int sum=0,b=arr[0];
for(int i=1;i<arr.length;i++){
if(b>0) b+=arr[i];
else b = arr[i];
if(b>sum) sum=b;
}
System.out.println(sum);
}
public static void main(String[]args){
int[] arr={1,3,-5,3,-2,5,-4,3};
maxSum(arr);
}
}
算法复杂度为O(n)
