題目連結 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/」
程式碼:
- #include <iostream>
- using namespace std;
- int main()
- {
- int n;
- cin >> n;
- int seq[n];
- for(int i = 0; i < n; i++)
- cin >> seq[i];
- int best_sum = INT_MIN;
- int current_sum = 0;
- for(int i = 0; i < n; i++)
- {
- current_sum = max(0, (current_sum + seq[i]));
- best_sum = max(best_sum, current_sum);
- }
- cout << best_sum << " " << endl;
- return 0;
- }
沒有留言:
張貼留言