121. Best Time to Buy and Sell Stock

Posted on | Edited on | Views:

LeetCode

link
One Pass


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur + prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }
}
/* implementation based on kadane's algorithm
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int[] d=new int[prices.length-1];
        for(int i=0;i<prices.length-1;i++) d[i]=prices[i+1]-prices[i];
        int localMax=0,globalMax=0;
        for(int i=0;i<d.length;i++){
            localMax=Math.max(d[i],d[i]+localMax);
            globalMax=Math.max(localMax,globalMax);
        }
        return globalMax;
    }
}*/

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// O(N^2)
class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        if(len==0) return 0;
        int min=Integer.MIN_VALUE;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                min=Math.max(prices[j]-prices[i],min);
            }
        }
        return min<=0?0:min;
    }
}

0%