https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Source

    int maxProfit(vector<int>& prices) {
		int profit = 0;
		FOR (i, prices.size()-1) {
			const int p = prices[i+1] - prices[i];
			if (p > 0) {
				profit += p;
			}
		}
		return profit;
	}

    int maxProfitIF(vector<int>& prices) {
		int profit = 0;
		int ud = -1;	// start with going down
		int pos = -1;
		FOR (i, prices.size()-1) {
			if (prices[i] < prices[i+1]) {
				if (ud < 0) {
					// go up
					pos = prices[i];
#ifdef TEST
					cout << "pos:" << pos << endl;
#endif
				}
				ud = 1;
			}
			else if (prices[i] > prices[i+1]) {
				if (ud > 0) {
					// go down
					if (pos >= 0) {
						profit += (prices[i] - pos);
#ifdef TEST
                        cout << "sell on " << prices[i] << " profit:" << prices[i] - pos << endl;
#endif
						pos = -1;
					}
				}
				ud = -1;
			}
			else {
                // ud = 0;  // No need!
			}
		}

		if (pos == -1) return profit;

		const int lastP = prices[prices.size()-1] - pos;
		if (lastP > 0) {
			profit += lastP;
		}

		return profit;
    }

    int maxProfitDP(vector<int>& prices) {
		const size_t n = prices.size();
        vvi dp(n, vi(n, 0));

		FOR(i, n) {
			if (i > 0) {
				if (dp[i][i] < dp[i-1][i-1]) {
					dp[i][i] = dp[i-1][i-1];
				}
			}
			FOR_INC(j, i+1, n) {
				const int p = prices[j] - prices[i];
				if (p > 0) {
					dp[i][j] = p;
					if (dp[j][j] < p + dp[i][i]) {
						dp[j][j] = p + dp[i][i];
					}
				}
			}
		}

#ifdef TEST
		PrintDP(dp);
#endif

		return dp[n-1][n-1];
    }
#ifdef TEST
	void PrintDP(const vvi& dp) {
		cout << "\t";
		FOR (j, dp[0].size()) {
			cout << setw(3) << j << ", ";
		}
		cout <<endl;
		FOR (i, dp.size()) {
			cout << i << "\t";
			FOR (j, dp[0].size()) {
				cout << setw(3) << dp[i][j] << ", ";
			}
			cout <<endl;
		}
	}
#endif

GitHub

• MaxProfit2