Leetcode: Maximum Subarray 了解分析

題目大意：在一個給定的數組中找到一個連續子數組，該子數組的和最大。

了解：在一個整型數組中找到一個和最大的子數組，傳回此最大和。本方法采用curSum來記錄目前的最大值，maxSum記錄查找過程中的最大值。時間複雜度為O(n)。

實作：

public class Solution {
    public int maxSubArray(int[] A) {
        if(A == null || A.length == 0)  return 0;
        int len = A.length;
        int curSum = A[0];
        int maxSum = A[0];
        for(int i = 1; i < len; i ++) {
            if(curSum < 0) {
                curSum = 0;
            }
            curSum += A[i];
            if(maxSum < curSum) {
                maxSum = curSum;
            }
        }
        return maxSum;
    }
}
           

給定數組：[-2,1,-3,4,-1,2,1,-5,4]，相鄰最大和子數組為[4,-1,2,1]，傳回6。

另：另外還有一種分治方法，待研究。