53. Maximum Subarray

 53. Maximum Subarray  ( https://leetcode.com/problems/maximum-subarray/ )

Given an integer array nums, find the subarray

 with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

 

Constraints:

1 <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

你可以用兩個迴圈 i 代表起點，j 代表終點
求得 i~j 的總和，保留最大的總和
i~j 的總和，可以用 i~(j-1) 的總和 + j
不需要每次都重新算 i+.....+j
這樣時間複雜度約 O(n^2)

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int max = INT_MIN;

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

        {

            int sum = 0;

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

            {

                sum += nums[j];

                if (sum > max)

                {

                    max = sum;

                }

            }

        }

        return max;

    }

};

有更快的 O(n) 解法
從第一個元素一路往後逐一加總
如果最大值的序列出現在   i~nums.size()
那就表示 0~(i-1) 的總和是負數
那最大值總和就不需要加上 0~(i-1) 的和
所以當 sum < 0  的時候，就重設 sum = 0
繼續求接下來 i~nums.size() 的總和即可

如果最大值的序列不包含最後一個元素
那表示最後一個元素是負數
i~ (nums.size()-1) 的總和，會 keep 在 max 之中
i~nums.size() 的總和，不會取代成為新的 max
同樣的如果最後 n 個元素的總和是負數
i~ (nums.size()-n) 的總和，會 keep 在 max 之中
i~nums.size() 的總和，不會取代成為新的 max

依此邏輯，只需要依序加總每個元素
當 sum >max，就更新 max
當 sum <0，就設 sum=0
這樣執行一次 for 迴圈，就可以得到最大的子序列和

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int max = INT_MIN;

        int sum = 0;

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

        {

            if (sum < 0)

            {

                sum = 0;

            }

            sum += nums[i];

            if (sum > max)

            {

                max = sum;

            }

        }

        return max;

    }

};

這邊要注意一下的是 sum 用 int 即可
因為 nums 內最大值是 10000，最多 100000 個，總和不會超過 1000000000
int 的最大值是2147483647，不會破表，所以用 int 就好

參考:
https://www.youtube.com/watch?v=cL5tRclvvCI&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=3