- 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[0];
- int len = nums.size();
- for (int i = 1; i <len; ++i) {
- curMax = curMax + nums[i]> nums[i] ? curMax + nums[i] : nums[i];
- result = curMax> result ? curMax : result;
- }
- return result;
- }
- };
写到这里, 我自己都没有想到就用动态规划的思想把这个题 bugfree 了. 有时, 看到别人想出一个好的方法也许并不是人家一开始就想到了, 而是通过从简单开始分析, 一点一点优化步骤, 得到好的思路和方法. 当然了, 有些题目可以从完全不同的两个方向去解决, 这时候换一种角度思考问题反而更重要.
来源: http://www.bubuko.com/infodetail-3101526.html