Best Time to Buy and Sell Stocks II Editorial

Practice Problem Link: Best Time to Buy and Sell Stocks II

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given an array prices where prices[i] denotes the price of a stock on the ith day. You want to maximize the profit by buying a stock and then selling it at a higher price.

Suppose you can do as many transactions as you want, what is the maximum profit that you can make?

Note:

• Return 0 if you cannot make a profit.
• You cannot buy/hold more than 1 stock at a time.
• You need to sell a stock before buying again.
• You can sell a stock and buy it again on the same day.

Naive Approach

The naive approach is to recursively calculate all the possible combinations of buying and selling stocks and find the combination that gives maximum profit.

Analysis

• Time Complexity: Exponential
• Auxiliary Space Complexity: O(n), Considering the recursive stack space.

Implementation

C++

int getMaxProfit (vector<int> &prices, int start, int end) {
	if (start >= end) {
		return 0;
	}
	int profit = 0, currentProfit = 0;
	for (int i = start; i <= end; i++) {
		for (int j = i + 1; j <= end; j++) {
			if (prices[j] > prices[i]) {
				currentProfit = prices[j] - prices[i] + getMaxProfit(prices, start, i - 1) + getMaxProfit(prices, j + 1, end);
			}
			profit = max(profit, currentProfit);
		}
	}
	return profit;
	
}
int maxProfit(vector<int> &prices) {
    return getMaxProfit(prices, 0, prices.size() - 1);
}

Java

class Solution {
	int getMaxProfit (int[] prices, int start, int end) {
		if (start >= end) {
			return 0;
		}
		int profit = 0, currentProfit = 0;
		for (int i = start; i <= end; i++) {
			for (int j = i + 1; j <= end; j++) {
				if (prices[j] > prices[i]) {
					currentProfit = prices[j] - prices[i] + getMaxProfit(prices, start, i - 1) + getMaxProfit(prices, j + 1, end);
				}
				profit = Math.max(profit, currentProfit);
			}
		}
		return profit;

	}
	int maxProfit(int[] prices) {
	    return getMaxProfit(prices, 0, prices.length - 1);
	}
}

Optimal Approach

The basic idea is to consider every local minima as a buying stock day and the next local maxima as a selling stock day. 

This can be done simply by traversing the given array and taking the sum of the difference between two consecutive elements if the difference is positive.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int maxProfit(vector<int> &prices) {
    int maximumProfit = 0;
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i - 1])
    	    maximumProfit += prices[i] - prices[i - 1];
       }
    return maximumProfit;
}

Java

class Solution {
	int maxProfit(int[] prices) {
        int maximumProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maximumProfit += prices[i] - prices[i - 1];
        }
        return maximumProfit;
	}
}