StockHistory srm 232 div2 hard

• 第i月に入る収入は、第i月以降で最もリターンの高い投資機会(株とタイミングの組み合わせ)に全額投資するのが最も効率的
• 上の考察をそのままコードに落とすだけ。
  • maxGain=1で初期化しているので、ループの最初のretの更新ではretは変化しない。けど、こうしておいた方が便利。
    • retの更新式をiのループの最後に持って来て、iのループの継続条件を i >= 1 にしても良い。しかし、この場合、iのループを抜けた後に、inititalInvestmentに掛け合わせるためのmaxGainの計算をiのループの外にもう一回書かないといけない。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class StockHistory{
public:
  vector<vector<int> > price;
  int n;
  int nstock;
  void print(){
    for(int i = 0; i < n; i++){
      copy(price[i].begin(), price[i].end(), ostream_iterator<int>(cout, "\t"));
      cout << endl;
    }
  }

  int maximumEarnings(int initialInvestment, int monthlyContribution, vector <string> stockPrices){
    n = stockPrices.size();
    price = vector<vector<int> >(n, vector<int>(0));
    for(int i = 0; i < n; i++){
      int buf;
      stringstream sst(stockPrices[i]);
      while(!sst.eof()){
	sst >> buf;
	price[i].push_back(buf);
      }
    }
    nstock = price[0].size();

    double ret = 0;
    int maxGainTerm = n - 1;
    int maxGainStock = 0;
    double maxGain = 1;
    for(int i = n - 2; i >= 0; i--){
      ret += (maxGain - 1) * monthlyContribution;
      for(int j = 0; j < nstock; j++){
	double tempGain = (double)price[n - 1][j] / price[i][j]; 
	if(maxGain < tempGain){
	  maxGainTerm = i;
	  maxGainStock = j;
	  maxGain = tempGain;
	}
      }
    }
    ret += (maxGain - 1) * initialInvestment;

    return ret;
  }



};