Problem Description
You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.
Key Insights
- You can make multiple transactions (buy and sell) on the same day.
- The goal is to capture every price increase to maximize profits.
- If the price on the next day is higher than the current day’s price, you should consider buying on the current day and selling on the next day.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The problem can be solved using a greedy approach. We iterate through the prices array and calculate the profit whenever there is a price increase from one day to the next. We keep a running total of these profits. The algorithm effectively uses a single pass through the array, making it efficient in both time and space. No additional data structures are needed apart from a few variables to maintain the total profit.