leetcode121 買賣股票最佳時機——dp

動态規劃

方程：

前i天最大收益=max{前i-1天最大收益，第i天的價錢-前i-1天的最小值}

c++實作

#include<bits/stdc++.h>
using namespace std;

int N;
int array[1000];
int ans;

int minarr(int array[], int a,int b){  //a，b之間的最小值，有a有b 
	int temp=999;
	for(int i=a;i<=b;i++){
		if(array[i]<temp){
			temp=array[i];
		}
	}
	return temp;
}

int max(int a,int b){
	return a>b?a:b;
}

int dp(int array[], int n){
	if(n==1){
		return array[1]-array[0];
	}else{
		return max(0, max(dp(array, n-1), array[n]-minarr(array,0,n-2)));
	}
}

int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>array[i];
	}
	ans=dp(array,N-1);
//	if(ans<0){
//		cout<<0;
//	}else{
//		cout<<ans;
//	}
	cout<<ans;
	return 0;
}
           

但是上述代碼沒法轉進leetcode的系統裡。。。

leetcode是用vector模闆實作的，

引用一個leetcode裡能跑的代碼，把遞歸用疊代實作，速度更快。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<=1) return 0;
        vector<int> maxp(prices.size());
        maxp[0] =0;
        maxp[1]=prices[1]-prices[0];
        int min=prices[0];
        
        for(int i=2;i<prices.size();i++){
            min=prices[i-1]<min?prices[i-1]:min;
            maxp[i]=max(maxp[i-1],prices[i]-min);
        }
        
        // return max(0, maxp[prices.size()-1]);
        return maxp[prices.size()-1]>0?maxp[prices.size()-1]:0;
    }
};
           

這裡面需要注意的是，三元運算符的速度高于max重載函數