Best Time to Buy and Sell Stock II

medium array greedy

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

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

Output7

Buy at 1, sell at 5 (+4). Buy at 3, sell at 6 (+3). Total 7 — equal to the sum of (5−1) + (6−3) = (5−1) is split into (1→2 etc). Equivalently, sum positive deltas: (5−1)+(3−5 skip)+(6−3)+(4−6 skip) = 4 + 3.

prices (comma-separated)

def max_profit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

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

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

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

Explanation

Because you can buy and sell as many times as you like, the best strategy is surprisingly simple: grab every upward move. Whenever tomorrow's price is higher than today's, that climb is free profit you can pocket.

The code walks through the prices and, for each consecutive pair, checks if prices[i] > prices[i - 1]. If so, it adds the difference prices[i] - prices[i - 1] to profit; if the price dropped, it simply skips that day.

This works because a long rise from a low to a high equals the sum of all the small daily rises in between. Buying at the bottom and selling at the top gives the exact same total as capturing each up-step, and we never have to capture any down-steps.

Example: prices = [7, 1, 5, 3, 6, 4]. The up-steps are 1→5 (+4) and 3→6 (+3); the drops 7→1, 5→3, and 6→4 are ignored. Total profit is 4 + 3 = 7.

Time: O(n) Space: O(1)