[DP題解] 求最大子數組和問題（問題拓展）
問題描述
最大連續子數組和
對一個有n個元素的數組，求最大的連續子數組的和，并求其開始、結束下标。
數組的元素必然有正數也有負數才有意義：
如果全是正數，那最大的子數組就是本身；
如果全部為負數，那最大子數組就是空數組（傳回最大和為0）；
如果數組的元素有正值有負值，那最大子數組的和一定為0或者正值。
例如下面的數組：-2,1,-3,4,-1,2,1,-5,4
這個問題中：
最大連續子數組和為：6；下标範圍為：[3,6]
如圖所示：
再例如給定數組：
算法設計：
1. 對于找出的最大連續子序列，用start代表開始元素下标；end代表結束元素下标。令：start = end = 0；
2. 設定變量max表示最大和，賦初值 max = 0；
3. 設定兩個變量 temp 和 ts，并賦初值均為0；
4. 從數組中的第一個元素開始周遊數組：
用temp用來存放從第一個數組元素開始的累加和；如果temp小于0，則說明這些數組元素之和為負值，不可能為最大值；是以将0指派給temp；同時 ts指派：ts=i+1。如果temp不小于0，則比較temp與max誰大；如果temp大于max，則記錄元素坐标start = ts，end = i；同時說明找到了新的最大值，那麼将temp中新的最大值賦給max，即： max = temp。
這裡需要注意：
（1）max 始終用來存放連續子序列的最大和； temp是一個臨時用于存放連續數組和的變量，一旦滿足 temp大于max，則進行指派操作，是max中始終存放的是最大和；
（2）對于temp而言：如果temp小于零，則說明之前累加和的元素和不是最大值。可以直接舍棄這些元素了。是以從目前元素（下标為i）之後的元素（ts = i+1）開始重新累加和。并且 temp = 0。
（可能元素都為負值；也可能有正值，負值，但是累加和為負值時，不可能成為最大和。根據題目要求最大和是0或者正值；當數組元素全為負值時，最大和為0）
public static void maxSum(int[] nums) {
int start = 0;
int end = 0;
int max = 0;
int temp = 0;
int ts = 0;
for (int i = 0; i < nums.length; i++) {
temp += nums[i];
if (temp < 0) {
ts = i + 1;
temp = 0;
} else {
if (temp > max) {
start = ts;
end = i;
max = temp;
}
}
}
System.out.println("maxSum = " + max + ", start : " + start + ", end = " + end);
}
完整的測試代碼如下：
package com.bean.algorithmexec;
public class MaxsumOfContinuousSubArray {
public static void maxSum(int[] nums) {
int start = 0;
int end = 0;
int max = 0;
int temp = 0;
int ts = 0;
for (int i = 0; i < nums.length; i++) {
temp += nums[i];
if (temp < 0) {
ts = i + 1;
temp = 0;
} else {
if (temp > max) {
start = ts;
end = i;
max = temp;
}
}
}
System.out.println("maxSum = " + max + ", start : " + start + ", end = " + end);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] demo = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
//int[] demo = new int[] { -2, -1, -3, -4, -1, -2, -1, -5, -4 };
/*
* 例如給定序列{ -2, 11, -4, 13, -5, -2 }，其最大連續子序列為{11,-4,13}，最大連續子序列和即為20。
* */
//int[] demo = new int[] { -2, 11, -4, 13, -5, -2 };
for (int i = 0; i < demo.length; i++) {
System.out.print(demo[i] + "\t");
}
System.out.println();
maxSum(demo);
}
}