程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode] Maximum Subarray

[LeetCode] Maximum Subarray

編輯:C++入門知識

[LeetCode] Maximum Subarray


Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray [4,?1,2,1] has the largest sum = 6.

click to show more practice.

解題思路:

題意為找出連續的和最大的子數組的和。可以有兩種方法來做,動態規劃以及分治法。

1、動態規劃。求最值問題一般可以考慮動態規劃的方法。d[i]表示子數組nums[k, i]的最大值,其中k>=0並且k

d[i] = nums[i], i==0 或者 d[i-1]<0
d[i] = nums[i] + d[i-1], 其他

然後返回d[]數組的最大值即可。這種方法的空間復雜度為O(n),其實可以優化成O(1)的空間復雜度。時間復雜度為O(n)

class Solution {
public:
    int maxSubArray(vector& nums) {
        int len = nums.size();
        if(len<1){
            return 0;
        }
        int d[len];
        d[0]=nums[0];
        int maxSum=nums[0];
        
        for(int i=1; i0){
                d[i]=nums[i]+d[i-1];
            }else{
                d[i]=nums[i];
            }
            maxSum = max(d[i], maxSum); 
        }
        
        return maxSum;
    }
};

2、分治法。這種方法非常巧妙。對於一個數組nums[left, right]來說,nums[mid]是其中間元素。最大值子數組的分布無非三種情況:

(1)最大值子數組在mid前面

(2)最大值子數組在mid後邊

(3)最大值子數組跨過mid

對於(1)(2),可以直接用遞歸來求得,對於(3),我們以mid向兩邊延伸找到最大的和。然後返回三種情況最大的一項即可。

空間復雜度為O(1),時間復雜度為O(n)

class Solution {
public:
    int maxSubArray(vector& nums) {
        return maxSub(nums, 0, nums.size() - 1);
    }
    
    int maxSub(vector& nums, int left, int right){
        if(left>right){
            return INT_MIN;
        }
        int mid = (left + right) / 2;
        int lMax = maxSub(nums, left, mid - 1);
        int rMax = maxSub(nums, mid + 1, right);
        int sum = 0;
        int lMaxSub = 0;
        for(int i=mid - 1; i>=left; i--){
            sum += nums[i];
            lMaxSub = max(sum, lMaxSub);
        }
        int rMaxSub = 0;
        sum = 0;
        for(int i=mid + 1; i<=right; i++){
            sum += nums[i];
            rMaxSub = max(sum, rMaxSub);
        }
        return max(max(lMax, rMax), lMaxSub + rMaxSub + nums[mid]);
    }
};


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved