• 向日葵朝着太阳转动, 时刻都在寻求当前汲取最大养分的可能。
  • 最优子结构就是追随太阳最高效的移动轨迹。
  • 移除重复子问题让向日葵紧跟太阳的脚步。
  • 贪心策略在一轮轮的简单选择中,逐步导向最佳的答案。

When greedy shines

Guaranteed to get the Global Optimal Solution

  • When we can’t find an counter-example with the greedy approach

Sub-optimal solution is good enough

Comparison with Dynamic Programming

Both rely on Optimal Substructure (最优子结构). However greedy

  • Find a locally optimal solution at each step without the need to consider decisions made previously
  • Dynamic Programming is determined to find global optimal
  • May or may not find the optimal solution
  • Often simple and efficient

Tips to Solve Greedy Problems

Greedy at different stages

  • We can use Greedy Loop more than once in a problem
  • For example, for question 1005, we use the first Greedy Loop to ensure all possible negative numbers are negated to positive numbers. Then, we can use the second Greedy Loop to negate the smallest positive integer when there is still negation left to use
  • The first Greedy Loop ensures we get the maximum value from negating the negative values in the array. The second Greedy Loop ensure we lose the least from negating array with all positive values

Obtain Optimal Substructure

  • One way to obtain Optimal Substructure is by sorting the given input
  • Basically limit the impact range of each element to its adjacent neighbours



  • For some questions, we can apply greedy loop more than once, for example the problem 1005 below




  • The order of the elements cant be altered, refer to Sub-Sequence





Stock Problems (股票买卖问题)

Greedy By Parts (2-Dimensions)

  • 135. Candy, we can be greedy to ensure proper distribution of candies on the left side, then greedy again to ensure proper distribution of candies on the right side. Then with both left and right, we are able to fulfil the requirement of Children with a higher rating get more candies than their 2 neighbors



Interval Problems (区间调度问题)

  • The trick is to think about finding the maximum range/reach

  • Use the smallest steps to increase the most amount of range/reach. We get the answer once the range/reach arrives at the last index of the given array

  • 55. Jump Game only has 1 range/reach to keep track of

  • 45. Jump Game II has 2 range/reach to keep track of, one is the maximum reach/range of current step, another one is the maximum reach/range of next step

  • 452,435, 56, we rely on sorting to make each entity next to each other, to form the Optimal Sub-structure to perform greedy algorithms






Greedy Loop

  • Looping through a collection, and apply a greedy algorithm on the elements

Local Optimal Solution

Global Optimal Solution