UVa12640 - Largest Sum Game(貪心)

題目大意

有一群人他們在玩 Largest Sum Game，主要就是在一個數列內要找出一個區間的總和最大，並輸出總和最大的數字。

題目連結

重點觀念

• 動態規劃 - 大衛的筆記
• stringstream 的使用，請點擊此連結查看教學

分析

• 基本上沒什麼好分析的XD
• 主要是我們從數列第一個開始，不斷累加，定義變數為 sum
  • sum + 數列第 i 值，不斷讓區間變更大
  • if(sum < 0) sum = 0，由於前面的區塊總和已經是負，因此捨棄前面的區間
    舉例：當 y,x 都是正數時，\(-y+x\) 不會比 \(x\) 大
  • if(sum > 0) comtinue，由於前面的區塊總和已經是正，因此保留前面的區間會讓數字總和更大
    舉例：當 y,x 都是正數時，\(y+x\) 會比 \(x\) 大
• 再來就是對每個數列時做 ans = max(ans, sum)，找到最大的 ans 就是答案

參考連結

Uva12640 - Largest Sum Game by txya900619

心得

水題XD，應該大家都會拉。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define DEBUG
#define int long long
#define MAXN 100020
using namespace std;
int n, temp;
vector<int> num;//debug 用數列
string q;
// istringstream insert ostringstream output
//https://stackoverflow.com/questions/3292107/whats-the-difference-between-istringstream-ostringstream-and-stringstream-w
stringstream ss;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    while(getline(cin, q)){
        ss.clear(); ss.str("");
        ss << q; //將數列字串放入 stringstream
        num.clear();

        int sum=0, max_sum=0;
        while(1){
            ss >> temp;
            //stringstream.fail() 如果剛剛沒有傳任何資料到變數就是 yes
            if(ss.fail()) break; 
            num.push_back(temp); //debug 用

            sum += temp; //不斷加入數列 i 值
            if(sum < 0) sum = 0; //捨棄前面區間
            max_sum = max(sum, max_sum); //看看現在區間，與 ans 誰比較大
        }
        cout << max_sum << '\n';

        #ifdef DEBUG
        //cout << num.size() << '\n';
        for(int i = 0; i < num.size(); i++) cout << num[i] << ' ';
            cout << '\n';
        #endif // DEBUG

    }

    return 0;
}