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.

Input: [7, 1, 5, 3, 6, 4] Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Input: [7, 6, 4, 3, 1] Output: 0
In this case, no transaction is done, i.e. max profit = 0.

Basically, assign two pointers which point to head and head->next, the left one p1 aims at the smaller price, while the right one p2 moves forward to find the higher price. if p1 > p2, move both pointers forward. By comparing the profit each move (when p1 < p2), we can find the maximum profit.

This solution is the implement of editorial solution, which maintains one pointer to update the profit by comparing current price to low_price.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int maxProfit(int* prices, int pricesSize) {
    int max = 0;
    int profit = 0;
    int low_price = prices[0];
    if(pricesSize<2){
        return 0;
    }
    for(int i = 0; i<= pricesSize -1; i++){
        if(*prices < low_price){
            low_price = *prices;
        }else{
            profit = *prices - low_price;
            if(max<profit){
                max=profit;
            }
        }
        prices = prices + 1;
    }
    return max;
}