台中女中程式解題系統：b026: 股海浮沈

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b026。

此題用 Kadane’s Algorithm：
https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm

Kadane's Algorithm 本身是 Dynamic Programming，圖文說明可參考這篇文章：「http://bedirtapkan.com/Kadane%27s-Algorithm-2/」

程式碼：

1. #include <iostream>  
2.   
3. using namespace std;  
4.   
5. int main()  
6. {  
7.     int n;  
8.     cin >> n;  
9.   
10.     int seq[n];  
11.     for(int i = 0; i < n; i++)  
12.         cin >> seq[i];  
13.   
14.     int best_sum = INT_MIN;  
15.     int current_sum = 0;  
16.   
17.     for(int i = 0; i < n; i++)  
18.     {  
19.         current_sum = max(0, (current_sum + seq[i]));  
20.         best_sum = max(best_sum, current_sum);  
21.     }  
22.   
23.     cout << best_sum << " " << endl;  
24.     return 0;  
25. }