算法：連續子數組的最大和

題目：給定一個數組 array[1, 4, -5, 9, 8, 3, -6]，在這個數字中有多個子數組，子數組和最大的應該是：[9, 8, 3]，輸出20，再比如數組為[1, -2, 3, 10, -4, 7, 2, -5]，和最大的子數組為[3, 10, -4, 7, 2]，輸出18。

解題思路：使用動規，dp[i]表示到當前位的最大和，有轉換方程：dp[i+1]=max(dp[i]+arr[i],arr[i])

<code>func main() {
    data:=[]int{2,0,-2,2,-2,-3,4}
    dp:=make([]int,len(data))
    dp[0]=data[0]
    ret:=0
    for i:=1;ib{
        return a
    }
    return b
}/<code>

面試中被問到的一個題。沒有在LeetCode上刷，自己寫的小demo。

關鍵字: 最大 array return