#2106
Maximum Fruits Harvested After at Most K Steps
expert · 1160 · lc hard +32 · verified · 61% accepted · 1,001 likes · top 61%
Description
Fruits are scattered at various positions along an infinite number line. You are given a 2D integer array fruits where fruits[i] = [positioni, amounti] indicates amounti fruits at position positioni. The array is sorted by position in ascending order with all positions unique.
You start at position startPos and may walk at most k steps in total (each step moves one unit left or right). Collecting all fruits at any position you visit, which then disappear.
Return the maximum total number of fruits you can collect.
Example 1:
Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
Output: 9
Explanation:
The optimal way is to:
- Move right to position 6 and harvest 3 fruits
- Move right to position 8 and harvest 6 fruits
You moved 3 steps and harvested 3 + 6 = 9 fruits in total.
Example 2:
Input: fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
Output: 14
Explanation:
You can move at most k = 4 steps, so you cannot reach position 0 nor 10.
The optimal way is to:
- Harvest the 7 fruits at the starting position 5
- Move left to position 4 and harvest 1 fruit
- Move right to position 6 and harvest 2 fruits
- Move right to position 7 and harvest 4 fruits
You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.
Example 3:
Input: fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
Output: 0
Explanation:
You can move at most k = 2 steps and cannot reach any position with fruits.
Code
1
2
3