Maximizing Stock Profits

The Problem & Greedy Strategy

Calculating the maximum profit achievable by buying and selling stocks over a sequence of days is a classic array manipulation problem frequently encountered in software engineering interviews. In this variant, you are provided with an array representing daily stock prices, and the goal is to determine the absolute highest cumulative profit you can earn by executing as many buy and sell transactions as you wish.

The constraint is that you cannot engage in multiple transactions simultaneously; you must sell your current stock before purchasing another.

This problem is solved efficiently in O(n) time using a Greedy Algorithm. Rather than trying to predict long-term trends or looking ahead multiple days, the algorithm makes the local optimal choice at each step: if tomorrow's price is higher than today's, we capture the gain.

Detailed Scenario Tracing

Let's trace exactly how the program evaluates two different price histories step-by-step:

Scenario A: Array arr = [100, 180, 260, 310, 40, 535, 695]

• Day 1 ($180): We compare today's price ($180) against yesterday's price ($100). Since $180 > $100, we execute a transaction. Profit added: 180 - 100 = 80. Total profit: 80.
• Day 2 ($260): Today's price ($260) is higher than yesterday's ($180). We capture the gain. Profit added: 260 - 180 = 80. Total profit: 160.
• Day 3 ($310): Today's price ($310) is higher than yesterday's ($260). Profit added: 310 - 260 = 50. Total profit: 210. (Note that adding the sequential differences 80 + 80 + 50 is mathematically identical to buying at $100 and selling at $310).
• Day 4 ($40): Today's price ($40) is less than yesterday's ($310). We do nothing.
• Day 5 ($535): Today's price ($535) is higher than yesterday's ($40). Profit added: 535 - 40 = 495. Total profit: 705.
• Day 6 ($695): Today's price ($695) is higher than yesterday's ($535). Profit added: 695 - 535 = 160. Total profit: 865.
• Result: The algorithm completes and returns $865.

Scenario B: Array arr1 = [4, 2, 2, 2, 4]

• Days 1, 2, and 3: The prices fall or remain flat (4 → 2 → 2 → 2). Since there is no positive change, no profit is added.
• Day 4 ($4): Today's price ($4) is higher than yesterday's ($2). Profit added: 4 - 2 = 2.
• Result: The algorithm returns $2.

Code Highlight & Mathematical Equivalence

The core loop logic in our Java solution checks for any positive daily movement:

if (arr[i] > arr[i - 1]) {
    profit += arr[i] - arr[i - 1];
}

This single check captures every segment of growth. Summing these individual intervals is mathematically equivalent to buying at the local minimum of a trend and selling at the local maximum, ensuring optimal results in a single pass.

The Java Code

Below is the complete, self-contained Java source code that demonstrates this greedy approach on our test scenarios.

package io.practise.accolite;
 
public class StockBuyAndSellMaxProfitChecker {
    public static void main(String[] args) {
        int arr[] = {100, 180, 260, 310, 40, 535, 695};
        int arr1[] = {4, 2, 2, 2, 4};
 
        System.out.println(getMaxProfit(arr1)); // Outputs: 2
        System.out.println(getMaxProfit(arr));  // Outputs: 865
    }
 
    private static int getMaxProfit(int[] arr) {
        int profit = 0;
 
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] > arr[i - 1]) {
                profit += arr[i] - arr[i - 1];
            }
        }
 
        return profit;
    }
}

Conclusion & Takeaways

By utilizing a greedy model, we avoid the complexity of recursive lookahead or sliding window trackers. Simply accumulating each positive increment ensures we trace the peaks and valleys of any price history array in a single O(n) pass.