LeetCode.121 買賣股票的最佳時機[DP]

![請添加圖檔描述](https://img-blog.csdnimg.cn/babf97b334dd4041941f56960e674ccf.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NjAyMTk0,size_16,color_FFFFFF,t_70)
           

一定要記住上來先列出轉換方程，而不是覺得有矩陣就是DP

int maxProfit(int* prices, int pricesSize){
    //前i天的最大收益 = max{前i-1天的最大收益,第i天的價格-前i-1天的最小價格}
    int i,j;
    int max = 0;
    int minP = prices[0];//前i-1天的最小價格

    //考慮第i天
    for(i=2;i<=pricesSize;i++){
        if(max < prices[i-1]-minP){
            max = prices[i-1] - minP;
        }
        if(prices[i-1] < minP){
            minP = prices[i-1];
        }
    }
    return max;
}
           

這是時間超限的代碼

int maxProfit(int* prices, int pricesSize){
    int i,j;
    int sum = 0,max = 0;
    for(i=0;i<pricesSize;i++){
        for(j=i+1;j<pricesSize;j++){
            sum = prices[j] - prices[i];
            if(sum>max){
                max = sum;
            }
        }
    }
    return max;
}