53. 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.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],Output: 6Explanation: [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.

Solution

Brute Force

1712 ms 13.3 MB

遍历所有子列，找出最大值

class Solution {
   public:    int maxSubArray(vector
   
    & nums) {
           int ans = nums[0];        for(int i = 0; i < nums.size(); i++)        {
               int sum = nums[i];            for(int j = i ; j < nums.size(); j++)            {
                   if(i == j) ans = max(ans,sum);                 else {
                       sum+=nums[j];                    ans = max(ans,sum);                }            }        }        return ans;    }};

这种情况下时间复杂度为O(n²)。

DP

动态规划=解决子问题+利用子问题的结果。

这个问题的子问题就是求解：最大子列和。

我们利用一个数组dp[ ] 来记录以当前index为结尾的子列的最大和。

下面逐步推导一下这个过程：

令dp[0] = nums[0]，当i == 1时，nums[1] = 1。若dp[i-1]为负，nums[i]为正，此时应该令dp[i] = nums[i]，所以此时最大子列和为1。

当i == 2时，nums[2] = -3。若dp[i-1]为正，nums[i]为负，此时应该令dp[i] = dp[i-1] + nums[i]，所以此时最大子列和为-2。

同理可得dp：

综上，dp[i]的取值有两种情况：

1.如果dp[i-1] > 0：dp[i] = dp[i-1] + nums[i]
2.如果dp[i-1] < 0：dp[i] = nums[i]

翻译成代码为dp[i] = (dp[i - 1] > 0 ? (dp[i - 1] + nums[i]) : nums[i] )

class Solution {
   public:    int maxSubArray(vector
   
    & nums) {
           int n = nums.size();        int* dp = new int[n];        dp[0] = nums[0];        int ans = dp[0];                for(int i = 1; i < n; i++){
               dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);            ans = max(ans, dp[i]);        }        return ans;    }};

可以发现使用DP后，时间复杂度降为O(n)

上一篇：[Easy] 58. Length of Last Word

下一篇：[Easy] 35. Search Insert Position

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

53. Maximum Subarray

Solution

Brute Force

DP

发表评论

最新留言

关于作者

推荐文章