53. 最大子数组和 – Blog of Aspirer

题目链接：https://leetcode.cn/problems/maximum-subarray/

仍然是只会最简单的暴力解法，不出意外的运行超出时间限制。。。

等研究官方题解再更新吧。。。。

官方的动态规划法已更新，看得有点迷，动态规划是个神奇的算法。。。。

class Solution {
public:
/*
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        for (int i = 0; i < nums.size(); i++) {
            for (int j = nums.size() - 1; j >= i; j--) {
                int s = 0;
                for (int k = i; k <= j; k++) {
                    s += nums[k];
                }
                if (s > sum) {
                    sum = s;
                }
            }
        }
        return sum;
    }
*/

    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxSum = nums[0];
        for (auto &x : nums) {
            pre = max(pre + x, x);
            maxSum = max(maxSum, pre);
        }
        return maxSum;
    }

};

class Solution {

public:

int maxSubArray(vector<int>& nums) {

int sum = nums[0];

for (int i = 0; i < nums.size(); i++) {

for (int j = nums.size() - 1; j >= i; j--) {

int s = 0;

for (int k = i; k <= j; k++) {

s += nums[k];

}

if (s > sum) {

sum = s;

}

return sum;

}

int maxSubArray(vector<int>& nums) {

int pre = 0, maxSum = nums[0];

for (auto &x : nums) {

pre = max(pre + x, x);

maxSum = max(maxSum, pre);

}

return maxSum;

}

};