pyhton 活力練習Day26
題目描述：
輸入一個整形數組（可能有正數和負數），求數組中連續子數組（最少有一個元素）的最大和。要求時間復雜度為O(n)。
輸入描述:
【重要】第一行為數組的長度N（N>=1）
接下來N行，每行一個數，代表數組的N個元素
輸出描述:
最大和的結果
思路：
本題主要考察的知識點：動態規劃
本題的思路可以轉化為：“對數組中的任意元素，若我們知道以它作為最后一個元素的所有連續子數組的最大和是多少，那么原問題的解就是在這n個最大和中最大的那個。
”再來看如何求解“對數組中的任意元素，若我們知道以它作為最后一個元素的所有連續子數組的最大和是多少”。因為有了2個限制條件“連續”、“它是最后一個”，那么問題又可以再次“減治”，等價于“若我們知道它上一個元素作為最后一個元素的所有連續子數組的最大和是多少，只要它不是負數，那么此問題就是它加上最后一個元素的值，否則直接用最后一個元素的值即可”。
以數組【1, -2, 3, 10, -4, 7, 2, -5】為例來進行說明：
遍歷數組：
| 結尾元素 | 可能取值 | 最大值 | 最終最大值 |
| 1 | 1 | 1 | 1 |
| -2 | 1+(-2)/-2 | -1 | 1 |
| 3 | -1+3/3 | 3 | 3 |
| 10 | 3+10/10 | 13 | 13 |
| -4 | 13+(-4)/-4 | 9 | 13 |
| 7 | 9+7/7 | 16 | 16 |
| 2 | 16+2/2 | 18 | 18 |
| -5 | 18+(-5)/-5 | 13 | 18 |
python代碼實現：
1 #輸入 2 def max_sum(): 3 #輸入的數據個數 4 N = int(input()) 5 #保存輸入的數據 6 input_N = [] 7 for _ in range(N): 8 input_N.append(int(input())) 9 #保存以每個元素結尾的最大值 10 s = [0 for _ in range(N)] #初始化 11 s[0] = input_N[0] 12 for i in range(1,N): 13 s[i] = s[i-1] + input_N[i] 14 s[i] = max(s[i],input_N[i]) 15 #計算以每個元素結尾的最大值（n個）的最大值 16 max_s = max(s) 17 18 return max_s 19 20 print(max_sum())
輸出結果：
浙公網安備 33010602011771號