動(dòng)態(tài)規(guī)劃之最大子段和問(wèn)題
問(wèn)題描述
有一個(gè)由呢個(gè)整數(shù)組成的數(shù)列A={a1每瞒，a2，......暇唾，an}促脉，截取其中從i - j開始的子段并計(jì)算字段和，求最大的字段和為多少策州？
例如A={1,3,-5,3,-2,5,-4,3}
則其最大字段和為3+（-2）+5 =6
使用動(dòng)態(tài)規(guī)劃算法求解問(wèn)題
假設(shè)最大子段和設(shè)為M
設(shè)從1到j(luò)中包括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);
}
}
算法復(fù)雜度為O(n)
