Given an integer array, prices[] of length n, containing the prices of the stocks on different days.
The task is to find the maximum profit possible for buying and selling the stocks on different days where unlimited transactions are allowed.
Stock must be bought before being sold.
Note: If the given array of prices is sorted in decreasing order, then no profit can be earned at all.
Input: prices[] = {100, 180, 260, 310, 40, 535, 695}
Output: 865
Input: prices[] = {4, 2, 2, 2, 4}
Output: 2
Solutions
Method 1: Memoization
We can solve this problem using recursion and memoization (DP).
The idea is to iterate over the array from left to right and keep track of a boolean flag "buy" (to identify if we buy or sell the stock).
In each iteration, we are either allowed to buy or sell the stock based on the "buy" flag.
In each iteration, we will return the maximum profit while selling/buying or not selling/buying the stock.
In the case of buying, the price[i] will be deducted from the profit, and in the case of selling, the price[i] will be added to the profit.
If we decide to buy or sell, we toggle the flag (buy).
Base Condition: Profit will be zero if all days are exhausted, i.e., i >= n.
Complexity
The time complexity of this solution is O(2^n) and space complexity is O(n).