[121] Best Time to Buy and Sell Stock

暴力法世界無敵慢 XD （廢話XD）
讓我想想 DP 可以怎麼寫 QQ
給一個array代表每天的股價
請找出最賺錢的賣法
也就是先出現的數字是買的價格, 後面賣的價格相減之後要達到最大.

Best Time to Buy and Sell Stock

int maxProfit(int* prices, int pricesSize) {

    int i,j, max = 0;

    

    for (i=0; i<pricesSize-1;i++)

        for(j=i+1;j<pricesSize;j++)

            if (prices[j]-prices[i] > max)

                max = prices[j]-prices[i];

    return max;

}

加上了一點點的判斷當然也是快不到哪裡去 XD

因為並沒有使用到DP的精神QQ

int maxProfit(int* prices, int pricesSize) {

    int i,j, max = 0;

    int min = INT_MAX;

    for (i=0; i<pricesSize-1;i++)

    {   

        if (prices[i]< min)

            min = prices[i];

        else 

            continue;

        for(j=i+1;j<pricesSize;j++)

            if (prices[j]-prices[i] > max)

                max = prices[j]-prices[i];

    }

    return max;

}

最後還是偷看了別人的解法XD

原來要這樣寫Orz

int maxProfit(int* prices, int pricesSize) {

    int i,j, max = 0;

    int min = INT_MAX;

    for (i=0; i<pricesSize;i++)

    {   

        if (prices[i]< min)

            min = prices[i];

        if (prices[i]-min > max)

            max = prices[i]-min;

    }

    return max;

}

順便記下最小值, 如果比之前小, 就更新min

畢竟往後出現的若是可以更大, 一定是減去min才最大的

若是前面的差值比較大, 那後面的差值減去min 還是小於差值, 那就不會被更新

像是 20, 100, 1, 10

雖然 1小於20

但後面的差沒有大於80的話就不會被更新

若是20, 100, 1, 90

89會被更新為最大差值.

[20231122 更新]

時隔數年～這個寫法跑起來已經是幾十 ms，完全不是當年的 6或8ms 啊 XD

測資不知道是多了多少？！

#define max(A,B) ((A>B)?(A):(B))

#define min(A,B) ((A<B)?(A):(B))

int maxProfit(int* prices, int pricesSize) {

int profit =0, price= 100000;

for (int i=0;i<pricesSize;i++)

{

profit = max (profit , prices[i]-price);

price = min(price, prices[i]);

}

return (price > 10000)? 0: profit;

}