[每日 LeetCode] 53. Maximum Subarray

Description：

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
​

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.

思路：本题要求数组的最大子序列和，考虑使用常规方法。定义两个变量 res 和 sum，其中 res 保存最终要返回的结果，即最大的子数组之和，sum 初始值为 0，每遍历一个数字 num，比较 sum + num 和 num 中的较大值存入 sum，然后再把 res 和 sum 中的较大值存入 res，以此类推直到遍历完整个数组，可得到最大子数组的值存在 res 中，返回 res 即可。

C++ 代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN, sum = 0;
        for (int num : nums) {
            sum = max(sum + num, num);
            res = max(res, sum);
        }
        return res;
    }
};
​

运行时间：12ms

运行内存：10.2M