我們再來做一題動態規劃問題吧．有點類似最長遞增子序列問題

題目是這樣的：

給定一個整數陣列nums，請在其中找到一個和最大的子陣列，然後返回其和．

例如輸入:nums=[-3,1,3,-1,2,-4,2]，會返回5，因為總和最大的子陣列是[1,3,-1,2]總和為5，注意子陣列需要是連續的，和子序列不同不能跳過．

思考

第一次看到這題，會想著使用前面學過的滑動視窗演算法，使用一個視窗找到一個解之後再壓縮．但是仔細思考後會發現，因為有負數的存在，因此滑動視窗最重要的，固定一邊後開始擴張或是縮小視窗的規則就不統一了．

例如視窗擴大時，可能遇到了一個負數，這樣總和有可能會增加或是減少，導致不知道什麼時候才能收縮左視窗，也就無法得到答案．

這體需要使用到動態規劃技巧，但是其dp的定義比較特殊，一般來說可能這樣定義

nums[0..i]中的最大子陣列和為dp[i]

但是這樣定義，會發現dp[i-1]與dp[i]沒有關聯性，由於子陣列需要連續性，所以可能兩個dp中是不連續的 ，舉個例子

nums = [1,2,-1,-2,100000]，這樣dp[3] ⇒ [1,2] =3 ，而dp[4] ⇒ [100000] = 100000，兩者沒有關聯性．

所以我們換個想法

以nums[i]為結尾的”最大子陣列和”為dp[i]

這樣的定義下，若要得到整個nums陣列的最大子陣列和，不能直接返回dp[n-1]，而是要遍歷整個dp陣列，找出最大的

var ans = Int.MAX_VALUE
    for(i in nums.indices){
        ans = Math.max(ans,dp[i])
    }
return ans

接下來，來撰寫狀態轉移方程．要怎麼從dp[i-1]轉移到dp[i]呢？

思考一下，因為子陣列要連續，所以dp[i]有兩種選擇

1.和前面的相鄰子陣列串連，形成一個總和更大的子陣列

2.不和前面的子陣列連結，自己重新當一個子陣列

這兩個選擇中，根據題目，需要選擇比較大的那個

//兩種選擇中選出比較大的那個
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])

有了狀態轉移方程，我們來寫出解法

fun maxSubArray(nums:IntArray):Int{
    val n = nums.size
    if(n ==0) return 0
    val dp = IntArray(n)
    //base case 第一個元素前面沒有子陣列 直接填入
    dp[0] = nums[0]
    //根據狀態轉移方程式，填滿dp 矩陣
    for(i in 1 until n){
        dp[i] = Math.max(nums[i],nums[i]+dp[i-1])//兩種選擇出比較大的那個
    }

    //找到nums的dp 矩陣中最大的值
    var ans = Int.MIN_VALUE
    for(k in 0 until n){
        ans = Math.max(ans,dp[k])
    }
    return ans
}

這題的解法時間複雜度只有O(n)，空間複雜度也是O(n)，已經很優秀了，但是可以發現我們的狀態轉移方程，dp[i]只跟前面一個dp[i-1]有關係，有沒有想到什麼？

對的，狀態壓縮

fun maxSubArray(nums:IntArray):Int{
    val n = nums.size
    if(n ==0) return 0
    val dp = IntArray(n)
    //base case 第一個元素前面沒有子陣列 直接填入
    dp[0] = nums[0]
    //狀態壓縮
    var dp0 = nums[0]
    var dp1 = 0
    var ans = dp0
    for(i in 1 until n){
        dp1 = Math.max(nums[i],nums[i]+dp0)
        dp0 = dp1
        ans = Math.max(ans,dp1)//同時計算最後結果
    }
    return ans
}

這樣這題的解法就很優雅了