[LeetCode53]Maximum Subarray

时间:2024-03-21 20:34:50

问题:

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