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