用动态规划算法实现最大子数组问题的算法
public class maxContinuousSubarrayDP {
public static void main(String[] args){
int[] input = {1,-2,4,5,-2,8,3,-2,6,3,7,-1};
int max = maxContinuousSubarrayDP(input, input.length);
System.out.println("最大值和"+max);
}
private static int maxContinuousSubarrayDP(int[] X, int n){
//初始化
int[] D = new int[n];
int[] Rec = new int[n];
D[n-1] = X[n-1];
Rec[n-1] = n-1;
//动态规划
//自底向上计算
for(int i=n-2; i>=0; i--){
//当后面的和大于0时
if(D[i+1]>0){
//记录子问题结果与决策
D[i] = X[i] + D[i+1];
Rec[i] = Rec[i+1];
}
//后面的数字和小于0
else{
D[i] = X[i];
Rec[i] = i;
}
}
//寻找解
int sMax = D[0];
for(int i=1; i<n; i++){
if(sMax<D[i]){
sMax = D[i];
System.out.println("开始位置下标"+(i+1));
System.out.println("结束位置下标"+Rec[i-1]+1);
}
}
return sMax;
}
}