[LeetCode] 53. Maximum Subarray* 解題思路 (Easy)

這題需要判斷最後加總是最大數字。

LeetCode 題目連結

 

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.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Accept 作法

這題時間複雜度為 O(n)。


Runtime: 0 ms
Memory: 39.2 MB

Java 程式碼

class Solution {
    public int maxSubArray(int[] nums) {
        int num = 0;
        int result =  Integer.MIN_VALUE;
        for(int i = 0;i<nums.length;i++){
            num = Math.max(nums[i] + num,nums[i]);
            result = Math.max(result,num);
            
        }
        return result;
    }
}

 

但是這題有提到要用 divide and conquer，故有另一種解法。時間複雜度為O(nlogn)

class Solution {
    public int maxSubArray(int[] nums) {
        return getMaxValue(nums,0,nums.length - 1);
    }
    
    public int getMaxValue(int[] nums, int left,int right){
        if(left >= right) return nums[left];
        int mid = left +(right - left)/2;
        int leftMax = getMaxValue(nums,left,mid-1);
        int rightMax = getMaxValue(nums,mid+1,right);
        
        int mmax = nums[mid], t = mmax;
        for(int i=mid -1; i >= left;--i){
            t+=nums[i];
            mmax = Math.max(mmax,t);
        }
        
        t = mmax;
        
        for(int i = mid+1; i<=right;++i){
            t+=nums[i];
            mmax = Math.max(mmax,t);
        }
        
        return Math.max(mmax,Math.max(leftMax,rightMax));
        
    }
    
    
}

更多 LeetCode 相關資源

• Udemy 暢銷 - Master the Coding Interview: Data Structures + Algorithms

 

複習程式面試書籍

除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。

書名：提升程式設計師的面試力：189道面試題目與解答

• 金石堂實體書資訊
• Hyread 電子書資訊

相關 LeetCode文章一律會放在 程式解題 標籤分類，歡迎持續追蹤。

⇒ 點我看更多程式解題