JZ42 连续子数组的最大和

发表于 分类于 本文字数： 475 阅读时长 ≈ 2 分钟

JZ42 连续子数组的最大和

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

$1<=n<=2×10^5$

$−100<=a[i]<=100$

要求:时间复杂度为 $O(n)$，空间复杂度为 $O(n)$

进阶:时间复杂度为 $O(n)$，空间复杂度为 $O(1)$

示例1

1
2
3
输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

1
2
输入：[2]
返回值：2

示例3

1
2
输入：[-10]
返回值：-10

题解

初见思路：终于还是到了最让我头痛的动态规划，动态规划的重点就是写出状态转移方程。

还是学艺不精，光记得状态转移方程了，让我自己定义状态定义不出来，找大Ｇ老师要来了思路一看就想起来了（一做就错:<）。

首先我们定义子问题$dp[i]$为以$nums[i]$为结尾的连续子数组的最大和，那么我们就可以去递推地计算$dp[i+1]$等等。

如果$nums[i]$就是$dp[i]$的起点，那么$dp[i]=nums[i]$
倘若这是以前的子数组的扩展，那么$dp[i] = dp[i-1]+nums[i]$

所以$dp[i] = max(nums[i],dp[i-1]+nums[i])$

边界条件：$i=0$时，$dp[0] = nums[0]$

只需要求得所有$dp[i]$中的最大值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        vector<int> dp;
        dp.push_back(array[0]);
        for(int i =1;i<array.size();i++){
            dp.push_back(max(array[i],dp[i-1]+array[i]));
        }
        return *max_element(dp.begin(), dp.end());
    }
};