leetcode53. 最大子序和

1、题目

https://leetcode-cn.com/problems/maximum-subarray/submissions/

2、题意

题解1：dp dp[i]表示 所有以i结尾的区间中的最大值
dp[0] = nums[0]；
两种情况 dp[i-1]>0就加上dp[i-1]
否则说明前面的数位负数 dp[i]等于nums[i];
执行用时:
4 ms, 在所有 C++ 提交中击败了97.37%的用户
内存消耗：7.1 MB, 在所有 C++ 提交中击败了100.00%的用户

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        dp[0] = nums[0];
        int maxn = nums[0];
        for(int i=1;i<nums.size();i++)
        {
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            maxn = max(dp[i],maxn);
        }
        return maxn;
    }
};

题解2：分治

本文地址：https://blog.csdn.net/weixin_46819595/article/details/107275036