[每日LeetCode] 53. Maximum Subarray

  |   0 评论   |   940 浏览

Description:

Given an integer arraynums, 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

评论

发表评论