Crack the Backend

Problem Statement

You are given an array prices where prices[i] is the price on day i. You may complete as many transactions as you like (buy one and sell one share multiple times). You may not hold more than one share at a time. Return the maximum profit you can achieve. (Each transaction is buy then sell; no overlapping holdings.)

Key Observations

Greedy: We can "simulate" optimal strategy by capturing every rise: whenever prices[i+1] > prices[i], we add prices[i+1] - prices[i] to profit (we buy at i and sell at i+1). This is equivalent to summing all positive consecutive differences. We never need to hold across a drop — selling before a drop and buying at the bottom is the same as summing the rises.

Approach

High-level: profit = 0. For i = 0 to n-2: if prices[i+1] > prices[i], profit += prices[i+1] - prices[i]. Return profit.

Steps: int profit = 0; for (int i = 0; i < prices.length - 1; i++) if (prices[i+1] > prices[i]) profit += prices[i+1] - prices[i]; return profit.

Implementation

Java

public int maxProfit(int[] prices) {
    int profit = 0;

    for (int i = 0; i < prices.length - 1; i++)
    if (prices[i+1] > prices[i]) {
        profit += prices[i+1] - prices[i];
    }

    return profit;
}

Test Cases

Example 1

Input

prices = [7,1,5,3,6,4]

Expected

7

Explanation

Buy 1 sell 5, buy 3 sell 6.

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.