標簽（空格分隔）： 動態(tài)規(guī)劃 分治法

傳送門：53. 最大子序和。

給定一個整數數組 nums ，找到一個具有最大和的連續(xù)子數組（子數組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數組 [4,-1,2,1] 的和最大，為 6。

進階:

如果你已經實現復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

分析：

總結：分類討論的標準是：若之前的和小于 0，則將最大和置為當前值，否則計算最大和。

思路1：動態(tài)規(guī)劃

下面展示了標準的動態(tài)規(guī)劃的寫法。

Java 代碼：

public class Solution {
    
    public int FindGreatestSumOfSubArray(int[] array) {
        int n = array.length;
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        dp[0] = array[0];
        int res = array[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Integer.max(dp[i - 1] + array[i], array[i]);
            res = Integer.max(res, dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{6, -3, -2, 7, -15, 1, 2, 2};
        Solution solution = new Solution();
        int findGreatestSumOfSubArray = solution.FindGreatestSumOfSubArray(nums);
        System.out.println(findGreatestSumOfSubArray);
    }
}

這道題主要就在狀態(tài)的定義上要思考一下，這里題目中的關鍵字是“連續(xù)”，所以如果我們定義的狀態(tài)就是題目要求的結果：dp[i] 表示 nums 在區(qū)間 [0,i] 中連續(xù)子數組的最大和，那么在思考狀態(tài)轉移方程的時候，dp[i] 之前的，例如 dp[i-1] 就有可能是是更前面的連續(xù)子數組的最大和，不利于我們分類討論。

因此，我們可以定義狀態(tài)：dp[i] 表示以 nums[i] 結尾的連續(xù)子數組的最大和。

這樣定義狀態(tài)，分類討論就變得容易多了，因為 dp[i-1] 表示一定以 nums[i-1] 結尾，那么 dp[i] 就可以有兩種情況：

1、把 nums[i] 直接接在 dp[i-1] 表示的那個數組的后面；

例如，dp[i-1] = 3，nums[i] = 5，當然接在后面，越接越大。

2、單獨的一個 nums[i] 。

這種情況也比較好想到，比如：dp[i-1] = -3，nums[i] = 5，加上前面的數反而我越來越小了，干脆我另起爐灶吧。

以上兩種情況的最大值就是 dp[i] 的值。

最后不要忘記了，最終的結果應該是把所有的 dp[0]，dp[1]，……，dp[n-1] 都看一遍，求最大值。

重點：動態(tài)規(guī)劃問題。狀態(tài)是：以當前數字為結尾的連續(xù)子數組的最大和。

Python 代碼：

class Solution(object):
    def maxSubArray(self, nums):
        """
            :type nums: List[int]
            :rtype: int
            """

        l = len(nums)
        if l == 0:
            return 0
        if l == 1:
            return nums[0]
        dp = [0 for _ in range(l)]
        dp[0] = nums[0]

        for i in range(1, l):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            # 最后不要忘記拉通求一遍最大值，或者在上面遍歷的時候，就保存最大值
            return max(dp)

或者你可以在遍歷的時候，就把最大值求出來。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l = len(nums)
        if l == 0:
            return 0
        # 以索引 i 結尾的最大子數組的和
        end_i_max = nums[0]
        # 最后返回的數
        res = nums[0]
        for i in range(1, l):
            # 例：[-3,1]
            end_i_max = max(nums[i], end_i_max + nums[i])
            res = max(res, end_i_max)
        return res

思路2：分治法

參考資料：連續(xù)子數組最大和

Python 寫法：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        return self.__max_sub_array(nums, 0, n - 1)

    def __max_sub_array(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = left + (right - left) // 2
        return max(self.__max_sub_array(nums, left, mid),
                   self.__max_sub_array(nums, mid + 1, right),
                   self.__max_cross_array(nums, left, mid, right))

    def __max_cross_array(self, nums, left, mid, right):
        """
        一定包含 nums[mid] 元素的最大連續(xù)子數組的和
        思路是看看左邊擴散到底，得到一個最大數
        右邊擴散到底得到一個最大數
        :param nums:
        :param mid:
        :param right:
        :return:
        """
        ls = 0
        j = mid - 1
        s1 = 0
        while j >= left:
            s1 += nums[j]
            ls = max(ls, s1)
            j -= 1

        rs = 0
        j = mid + 1
        s2 = 0
        while j <= right:
            s2 += nums[j]
            rs = max(rs, s2)
            j += 1

        return ls + nums[mid] + rs


if __name__ == '__main__':
    s = Solution()
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    result = s.maxSubArray(nums)
    print(result)

（本節(jié)完）