122. Best Time to Buy and Sell Stock II

Posted on | Edited on | Views:

LeetCode

Brute Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// In this case, we simply calculate the profit corresponding to all the possible sets of transactions 
// and find out the maximum profit out of them.
class Solution {
    public int maxProfit(int[] prices) {
        return calculate(prices, 0);
    }

    public int calculate(int prices[], int idx) {
        if (idx >= prices.length) return 0;
        int max = 0;
        for (int start = idx; start < prices.length; start++) {
            for (int i = start + 1; i < prices.length; i++) {
                if (prices[start] < prices[i]) {
                    int profit = prices[i] - prices[start] + calculate(prices, i + 1);
                    if (profit > max) max = profit;
                }
            }
        }
        return max;
    }
}


Greedy

1
2
3
4
5
6
7
8
9
class Solution {
    public int maxProfit(int[] prices) {
        int max_profit=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1]) max_profit+=prices[i]-prices[i-1];
        }
        return max_profit;
    }
}

0%