Leetcode之53. Maximum Subarray Easy

Leetcode 53 Maximum Subarray Easy
https://leetcode.com/problems/maximum-subarray/
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

分析：
本题虽然标的是一道easy题，但刚开始做我是没有思路的。那么，就思考，如果暴力解决这道题该怎么做？那就对每次遍历到的元素和它之前的连续元素进行求和，看是否大于目前的最大和值，时间复杂度为O(n^2)。在演草纸上做这个过程时，你就会发现，这么做效率不高：在遍历到当前元素做连续元素相加这个操作时，前一个元素做了类似操作，所以实际上可以利用前一个元素的计算结果。但是，这样依然不能减少时间复杂度，怎么办？还可以接着想，遍历到当前元素时，我们不必要对其之前的连续元素进行累加计算，只需要对之前产生最大累加和的连续元素的结果进行累加即可。这样，我们可以这么做：用一个变量来存放之前元素的最大累加和（注意，这里面必须包含前一个元素），用另一个变量来存放最大值这个结果。这个方法的时间复杂度是O(n)。程序可以这么写：

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int curMax, result;

        curMax = result = nums[];

        int len = nums.size();

        for (int i = ; i < len; ++i) {

            curMax = curMax + nums[i] > nums[i] ? curMax + nums[i] : nums[i];

            result = curMax > result ? curMax : result;

        }

        return result;

    }

};

写到这里，我自己都没有想到就用动态规划的思想把这个题bugfree了。有时，看到别人想出一个好的方法也许并不是人家一开始就想到了，而是通过从简单开始分析，一点一点优化步骤，得到好的思路和方法。当然了，有些题目可以从完全不同的两个方向去解决，这时候换一种角度思考问题反而更重要。

巴特西

Leetcode之53. Maximum Subarray Easy

最新文章

热门文章