[leet code] 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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

該題思路最重要, 最初想法是儲存所有結果為正的子數組的sum到一個建立數組當中, 然後再提取該結果數組最大值作為傳回值.  但經過多次嘗試能無法實作.

經網上搜尋後發現可以引入一個max變量動态儲存子數組結果, 使得隻有子數組最大值被保留并用于與新的子數組結果進行比較.  另一方面, 隻要子數組的選取不需要考慮大小比較, 而隻要結果為正則繼續增加下一個數組元素.

public class Solution {
    public int maxSubArray(int[] A) {
        int sum = 0;
        int max = Integer.MIN_VALUE;// ensure the initial value < all the array elements
        
        for (int i=0; i<A.length; i++){
            // keep culculating sum of subarray
            sum += A[i];
            // keep the max sum of subarrays
            max = Math.max(max,sum);
            // reset sum if sum<0; if all the array elements < 0, then return the single largest array element
            if(sum<0) sum = 0;
        }
        return max;
    }
}
           

Divide and conquer approach:

這是目前接觸到的最難的題目(做的題還很少).  即使是看了别人的解決方法還需要很長一段時間了解.  該解決方法的思路是将最大subarray的情況分成三種:

1. 最大subarray完全在數組中點左邊

2. 最大subarray完全在數組中點右邊

3. 最大subarray經過數組中點

然後在得到情況1和情況2的時候都使用遞歸, 而為了了解這個做法我曾經manually模拟運作, 過程感覺比較複雜.  回歸的程式的實際當中其實可以不需要考慮到每一步的細節兒隻需要考慮一下幾點:

1. 遞歸的輸入

2. 遞歸的輸出

3. 遞歸的出口

于是回到本體思路, 在計算最大subarray的函數當中, 我需要計算上面提到的三種情況subarray的最大值, 再從這三種情況的最大值當中選最大值作為傳回.

note: 經過遞歸, 情況1 和情況2 其實都會最終回到情況3. 另, midLeftMax 與midRightMax沒有使用MIN_VALUE, 因為在所有subarray元素都為負值時, 隻有最小元素會傳回.  而在情況3下(subarray會經過中點), 傳回的隻可能是中點, 于是左右均可以設為0;

public class Solution {
    public int maxSubArray(int[] A) {
        if (A.length == 0) return Integer.MIN_VALUE;
        
        int sumMax = Integer.MIN_VALUE;
        return findSubSum(A, 0, A.length-1, sumMax);
    }
    
    // recursive function
    public int findSubSum(int[] A, int left, int right, int sumMax){
        // recursive exit
        if(left>right) return Integer.MIN_VALUE;
        
        int mid = (left+right)/2;
        //case left
        int leftMax = findSubSum(A, left, mid-1, sumMax);
        // case right
        int rightMax = findSubSum(A, mid+1, right, sumMax);
        
        // case cross mid
        int sum = 0;
        // mid->left
        int midLeftMax = 0;
        for (int i=mid-1; i>=left; i--){
            sum += A[i];
            midLeftMax = Math.max(midLeftMax, sum);
        }
        
        //mid->right
        int midRightMax = 0; sum=0;
        for (int i=mid+1; i<=right; i++){
            sum += A[i];
            midRightMax = Math.max(midRightMax, sum);
        }
        
        //max sum
        sumMax = Math.max(Math.max(leftMax, rightMax), midLeftMax+midRightMax+A[mid]);
        return sumMax;
    }
}