Leetcoed dp问题 53. 最大子数组和

53. 最大子数组和
    

暴力解法（超时）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        int maxSum = -100000;
        int sum = 0;
        for(int i = 0;i<len;i++){
            sum = 0;
            for(int j = i;j<len;j++){
                sum+=nums[j];
                maxSum = max(maxSum,sum);
            }
        }
        return maxSum;
    }
};

贪心算法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //https://leetcode.cn/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/
        int result = INT_MIN;;
       int len = nums.size();
       int sum = 0;
       for(int i = 0;i<len;i++){
           sum +=  nums[i];
           result = max(result,sum);
           if(sum < 0) sum = 0;
       }
       return result;
    }
};

动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        for(int i = 1;i<len;i++){
            if(nums[i-1] > 0) nums[i]+=nums[i-1];
        }
        return *max_element(nums.begin(),nums.end());
    }
};