53. 最大子序和

Description

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

Analyze

给定的函数如下：

• @param nums 一个数组
• @param numsSize 数组长度
• @return 最大和

这题可以先求前缀和转变一下思路，当求出前缀和后问题就变成了在前缀和数组中找两个数的差的最大值，这个是一个动态规划的思想，因此这题用前缀和+动态规划就可以解决了。
前缀和好办，那动态规划呢？通项公式怎么找？我们着重考虑第 i 项，对于动态规划，无非就是选或是不选，如果选第 i 项，那么数组前 i 项中两数差的最大值就等于第 i 项的值减去前 i-1 项中最小的值；如果不选第 i 项，那么那么数组前 i 项中两数差的最大值就等于第 i-1 项得到的最大值，而我们需要的是这两者之间更大的那个作为动态规划数组的第 i 项，可以总结为下面的公式：

假设 pre 表示前缀和数组，opt 表示动态规划的数组，i 表示数组下标，min 表示前 i 项前缀和数组中最小的数，那么动态规划数组的通项公式为：

opt[ i ] = max{ pre[ i ] - min，opt[ i - 1 ] }

opt 数组中的最后一项就是题中的最大值

Realization

• 构建前缀和数组

  
  
• 构建动态规划数组以及更新 min 的值

这里一开始定义 min 为数组第 0 个元素，随后又通过一个判断改变了，因为min 只能是数组中出现过的值，但是有这么一种情况：

原数组为{ 1，1 }，前缀和数组为{ 1，2 }，此时一开始 min 值为1，opt[ 0 ]为1，后续给opt[ 1 ]赋值的时候因为min 为1，所以计算了 pre[ i ] - 1，但实际上呢，这个时候pre[ i ]本可以不减的，不减就意味着直接取pre[ i ]，即前 i 项的和为2，而减了之后是第 i 项的和了，也就是说，一开始给min 赋值了之后，后续pre[ i ] - min就取不到pre[ i ]的值了，他必须减掉一个，因此我们给min 加个判断。
这里可以这么思考，如果给定的数组全是正数，显然满足题意的值应该是数组所有数的和，但由于min 的存在，必须要减掉第 0 个值，这显然是不对的，所以给它做了调整

• 返回动态规划数组中的最后一个值

  
  

• 提交

  
  

Dictionary

附源代码

int maxSubArray(int* nums, int numsSize){
    int* pre = (int*)malloc(sizeof(int) * numsSize);
    pre[0] = nums[0];
    for(int i = 1; i < numsSize; ++i)
    {
        pre[i] = pre[i-1]+nums[i];
    }
    int* opt = (int*)malloc(sizeof(int) * numsSize);
    int min = pre[0];
    if(pre[0] > 0)min = 0;
    opt[0] = pre[0];
    for(int i = 1; i < numsSize; ++i)
    {
        opt[i] = opt[i-1]>pre[i]-min ? opt[i-1] : pre[i]-min;
        min = min<pre[i] ? min : pre[i];
    }
    return opt[numsSize-1];
}