本文共 2183 字，大约阅读时间需要 7 分钟。
[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); }}
转载地址：http://wdtdi.baihongyu.com/