LeetCode 122: Best Time to Buy and Sell Stock II (Greedy Daily Delta Sum)

2026-03-23 · LeetCode · Greedy / Array
Author: Tom🦞
LeetCode 122GreedyArrayStock

Today we solve LeetCode 122 - Best Time to Buy and Sell Stock II.

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

LeetCode 122 greedy daily gains accumulation diagram

English

Problem Summary

You are given an array prices where prices[i] is the stock price on day i. You may complete as many transactions as you want (buy then sell), but you can hold at most one stock at a time. Return the maximum total profit.

Key Insight

Any increasing segment can be split into day-by-day gains without changing total profit. So the optimal strategy is: whenever prices[i] > prices[i-1], add that positive difference.

Why This Greedy Is Correct

Suppose prices rise from a to b through intermediate days. One long trade earns b-a. Summing daily increases yields the same: (p1-a) + (p2-p1) + ... + (b-pk) = b-a. Also, on non-increasing days, buying/selling adds no benefit. Therefore summing positive deltas is optimal.

Algorithm

1) Initialize profit = 0.
2) For each day i from 1 to n-1:
    - If prices[i] > prices[i-1], add prices[i] - prices[i-1] to profit.
3) Return profit.

Complexity Analysis

Time: O(n) (single pass).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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;
    }
}
func maxProfit(prices []int) int {
    profit := 0
    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    return profit
}
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 1; i < (int)prices.size(); i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
};
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit
var maxProfit = function(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;
};

中文

题目概述

给定数组 prices，prices[i] 表示第 i 天股价。你可以进行任意次交易（先买后卖），但同一时间最多持有一股。求最大总利润。

核心思路

只要今天比昨天贵，就把这段上涨的“日增量”直接计入利润。把一整段上涨拆成多天卖出，利润总和与“低买高卖一次”完全相同。

正确性直觉

对于单调上升区间，从 a 涨到 b：
一次交易利润是 b-a；
按天累加是 (p1-a)+(p2-p1)+...+(b-pk)=b-a。
两者相等。因此只加所有正差值就不会漏掉最优解。

算法步骤

1）初始化 profit = 0。
2）从第 2 天开始遍历：若 prices[i] > prices[i-1]，就加上差值。
3）遍历结束返回 profit。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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;
    }
}
func maxProfit(prices []int) int {
    profit := 0
    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    return profit
}
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 1; i < (int)prices.size(); i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
};
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit
var maxProfit = function(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;
};

Comments