题解33 | #动态规划#连续子数组的最大和#

1.动态规划——时间复杂度O(n)，空间复杂度O(n)

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param array int整型vector 
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        vector<int>sum(array.size());
        int max = array[0];
        for(int i = 0; i < array.size(); i++){
            sum[i] = std::max(sum[i-1] + array[i] , array[i]);
            max = std::max(max , sum[i]);
        }
        return max;
    }
};

2.基本算法思想

设动态规划列表 dp，dp[i] 代表以元素 array[i] 为结尾的连续子数组最大和。状态转移方程： dp[i] = Math.max(dp[i-1]+array[i], array[i]);

具体思路如下：

1.遍历数组，比较 dp[i-1] + array[i] 和 array[i]的大小;

2.为了保证子数组的和最大，每次比较 sum 都取两者的最大值;

3.用max变量记录计算过程中产生的最大的连续和dp[i]；

3.完整实例

#include<iostream>
using namespace std;
int a[200000],dp[200000];
int main(){
    int n,i;
    cin>>n;
    //从0开始
    for(i = 0;i < n;i++){
        cin>>a[i];
    } 
    //初始化一下
    dp[0] = a[0];
    int res = dp[0];
    //从1开始防止数组溢出
    for(i = 1;i < n; i++){
        dp[i] = std::max(dp[i-1] + a[i] , a[i]);
        res = std::max(res , dp[i]);
    }
    cout<<res;
    return 0;
}
// 64 位输出请用 printf("%lld")

示例1

输入：

8
1 -2 3 10 -4 7 2 -5

输出：

18

说明：

经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18