LeetCode OJ:Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

設dp[i]為前i個元素（包括第i個元素）的最長連續子序列和，

則有dp[i+1]=max(0,dp[i]+prices[i]-prices[i-1])，答案就是dp[0]到dp[n-1]的最大值

class Solution{
public:
	int maxProfit(vector &prices){
		int dp=0;
		int maxV=0;
		for(int i=1;i

answer2:
設dp[i]為前i個元素（不一定包括第i個元素）的最長連續子序列和
則有dp[i+1]=max{dp[i]，prices[i+1]-前i+1項的價格的最小值}

class Solution{
public:
	int maxProfit(vector &prices){
	    if(!prices.size())return 0;
		int dp=0;
		int minP=prices[0];
		for(int i=1;i

answer3:
與answer2類似，設dp[i]為i到n-1的最長子序列和
則有dp[i-1]=max{dp[i],後i-1至n-1的價格最大值-prices[i]}
class Solution{
public:
	int maxProfit(vector &prices){
	    if(!prices.size())return 0;
		int dp=0;
		int maxP=prices[prices.size()-1];
		for(int i=prices.size()-2;i>=0;i--){
			maxP=max(maxP,prices[i]);
			dp=max(dp,maxP-prices[i]);
		}
		return dp;
	}
};