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;
	}
};