[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);
}
}