台中女中程式解題系統: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. }  

沒有留言: