思路概述

I、非常常規(guī)的動態(tài)規(guī)劃問題，遞推公式就是dp[i] = max(nums[i], nums[i] + dp[i-1])， 在當(dāng)前i位置判斷是否舍棄i及i前面的加和結(jié)果，比當(dāng)前數(shù)字優(yōu)就不舍棄， 即dp[i-1]得大于零，也就是歷史結(jié)果得大于零才有延續(xù)下去的價(jià)值。
II、兩個(gè)數(shù)組相互無法重疊，必定是一個(gè)在左，一個(gè)在右，那么從正反兩個(gè)方向求出I中的dp_lift[i][0]、dp_right[i][0]記錄從左、從右必定加上當(dāng)前值情況下的局部最優(yōu)解，dp_lift[i][1]、dp_right[i][1]記錄從左、從右無論當(dāng)前值加不加情況下的全局最優(yōu)解。最后求出

max(dp_lift[i][1]+dp_right[i][1])

即可。
III、特殊動態(tài)規(guī)劃問題，Local[i][j]表示在到達(dá)數(shù)組中第i個(gè)數(shù)時(shí)， 有j個(gè)子數(shù)組， 并且第i個(gè)數(shù)一定在子數(shù)組中，此為局部最優(yōu)。Global[i][j]為在到達(dá)數(shù)組中第i個(gè)數(shù)時(shí)， 有j個(gè)子數(shù)組， 第i個(gè)數(shù)不一定在子數(shù)組中，此為全局最優(yōu)。

Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + nums[i-1]=max(Local[i-1][j]+ nums[i-1], Global[i-1][j-1]+ nums[i-1])

Local[i-1][j]+ nums[i-1]表示把第i個(gè)數(shù)加入到有著第i-1個(gè)數(shù)的第j個(gè)子數(shù)組，Global[i-1][j-1]+ nums[i-1]表示用第i個(gè)數(shù)新產(chǎn)生第j個(gè)子數(shù)組，max(Local[i-1][j]+ nums[i-1], Global[i-1][j-1]+ nums[i-1]) 表示對這種兩種選擇狀態(tài)進(jìn)行擇優(yōu)。

Global[i][j] = max(Local[i][j], Global[i-1][j])

特別注意，遞推公式的max函數(shù)實(shí)際上代表了對過去狀態(tài)產(chǎn)生的多個(gè)結(jié)果進(jìn)行擇優(yōu)。

I

描述

給定一個(gè)整數(shù)數(shù)組，找到一個(gè)具有最大和的子數(shù)組，返回其最大和。
子數(shù)組最少包含一個(gè)數(shù)。

樣例

給出數(shù)組[?2,2,?3,4,?1,2,1,?5,3]，符合要求的子數(shù)組為[4,?1,2,1]，其最大和為6

代碼

class Solution:
    """
    @param nums: A list of integers
    @return: A integer indicate the sum of max subarray
    """
    def maxSubArray(self, nums):
        # write your code here
        dp = [0 for i in range(len(nums))]
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
        return max(dp)

II

描述

給定一個(gè)整數(shù)數(shù)組，找出兩個(gè) 不重疊 子數(shù)組使得它們的和最大。
每個(gè)子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的。
返回最大的和。
子數(shù)組最少包含一個(gè)數(shù)。

樣例

給出數(shù)組 [1, 3, -1, 2, -1, 2]
這兩個(gè)子數(shù)組分別為 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它們的最大和都是 7

挑戰(zhàn)

要求時(shí)間復(fù)雜度為 O(n)

代碼

class Solution:
    """
    @param: nums: A list of integers
    @return: An integer denotes the sum of max two non-overlapping subarrays
    """

    def maxTwoSubArrays(self, nums):
        # write your code here
        dp_lift = [[0, 0] for i in range(len(nums))]
        dp_right = [[0, 0] for j in range(len(nums))]

        dp_lift[0][0] = nums[0]
        dp_lift[0][1] = nums[0]
        for i in range(1, len(nums)):
            dp_lift[i][0] = max(nums[i], nums[i] + dp_lift[i - 1][0])
            dp_lift[i][1] = max(dp_lift[i][0], dp_lift[i - 1][1])
        dp_right[-1][0] = nums[-1]
        dp_right[-1][1] = nums[-1]
        for i in reversed(range(0, len(nums) - 1)):
            dp_right[i][0] = max(nums[i], nums[i] + dp_right[i + 1][0])
            dp_right[i][1] = max(dp_right[i][0], dp_right[i + 1][1])
        result = -10000
        for i in range(0, len(dp_lift)-1):
            result = max(result, dp_lift[i][1] + dp_right[i+1][1])
        return result

III

描述

給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，找出 k 個(gè)不重疊子數(shù)組使得它們的和最大。每個(gè)子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的。
子數(shù)組最少包含一個(gè)數(shù)。

樣例

給出數(shù)組 [-1,4,-2,3,-2,3] 以及 k = 2，返回 8

代碼

class Solution:
    """
    @param nums: A list of integers
    @param k: An integer denote to find k non-overlapping subarrays
    @return: An integer denote the sum of max k non-overlapping subarrays
    """
    def maxSubArray(self, nums, k):
        # write your code here
        minNum = min(0, min(nums) - 1)
        Local = [[0 for i in range(k + 1)] for i in range(len(nums) + 1)]
        Global = [[0 for i in range(k + 1)] for i in range(len(nums) + 1)]

        for j in range(1, k+1):
            Local[0][j] = minNum
            Global[0][j] = minNum
        for i in range(1, len(nums)+1):
            for j in range(1, k+1):
                if j > i:
                    Local[i][j] = minNum
                    Global[i][j] = minNum
                else:
                    Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + nums[i-1]
                    Global[i][j] = max(Local[i][j], Global[i-1][j])
        return Global[-1][-1]

題目來源

https://www.lintcode.com/problem/maximum-subarray-i/description
https://www.lintcode.com/problem/maximum-subarray-ii/description
https://www.lintcode.com/problem/maximum-subarray-iii/description