问题:
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4]
,
the contiguous subarray [4,−1,2,1]
has the largest sum = 6
思路:题意为给定 n 个整数(可能为负数)组成的序列 a[1],a[2],a[3],...,a[n],求该序列如
a[i]+a[i+1]+...+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为
0,如果序列中全部是负数则最大子断和为0,依此定义,所求的最优值为 Max{0,a[i]+a[i+1]+...+a[j]},1≤i≤j≤n。
例如 输入:-2,11,-4,13,-5,-2
输出:20
则此题可通过动态规划求解
首先计算辅助数组。
接着计算辅助数组的最大值。
辅助数组b[j]用来记录一j为尾的子段和集合中的最大子断和。
例如,假如有一序列:-2,11,-4,13,-5,-2
则
b(1) = -2 ,b(2) = 11, b(3) = 7, b(4) = 20, b(5) = 15, b(6) = 13
a(1) = -2, a(2) = 11, a(3) = 7, a(4) = 13, a(5) = -5, a(6) = -2
b(1) < 0 b(2) > 0 b(3) > 0 b(4) > 0 b(5) > 0 b(6) > 0
---->
{ b(j - 1) + a(j) 当b(j-1) >= 0
b(j) = {
{a(j) 当b(j-1) < 0
代码:
public class Solution {
public int MaxSubArray(int[] nums) {
int sum = ;
int[] dp = new int[nums.Length];
int temp = ;
for(int i = ; i < nums.Length; i++)
{
if(temp > )
temp += nums[i];
else
temp = nums[i];
dp[i] = temp;
}
sum = dp[];
for(int i = ; i < dp.Length; i++)
{
if(sum < dp[i])
sum = dp[i];
}
return sum;
}
}