UVa 12640 : Largest Sum Game

問題リンク : http://uva.onlinejudge.org/external/126/p12640.pdf

問題概要 :
長さNの数列が与えられる
この中から連続するいくつかの数字を選び、それらの和をとる
この値の最大値を求めよ

解法 :
数列を a とし、各要素は a[i] ( 0 <= i < N ) とする
a[0]から順番に見ていく
今みている場所からそれより前で作れる和の最大値は、
今みている場所を i とすると
( a[0] から a[i] までの総和 ) - ( a[0] から a[j] までの総和の最小値 )、　または ( a[0] から a[i] までの総和 ) となる
ただし j は 0 以上 i 未満の整数
単純にループを回しながら a[0] からの最小値を記録しておけば良い
各要素の最大値も忘れないこと

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main(){
  string s;
  while( getline(cin,s) ){
    vector<int> vec;
    stringstream ss; ss << s;
    int maxi = 0, mini = 0, sum = 0;
    while( !( ss >> s ).fail() ) { vec.push_back((atoi)(s.c_str())); maxi = max(maxi,vec.back()); }
    rep(i,vec.size()){
      mini = min(mini,(sum+=vec[i]));
      maxi = max(maxi,max(sum-mini,sum));
    }
    cout << maxi << endl;
  }
  return 0;
}