Post

Leetcode Day 24 - Greedy: Stock and Jump Problems

122 Best Time to Buy and Sell Stock II | 55 Jump Game | 45 Jump Game II | 1005 Maximize Sum Of Array After K Negations

Posted Updated
By Le Lyu
views 8 min read

Greedy Algorithm

DiffProblemPythonJava
Medium122 Best Time to Buy and Sell Stock II✅ 
Medium55 Jump Game✅ 
Medium45 Jump Game II✅ 
Easy1005 Maximize Sum Of Array After K Negations✅ 

Best Time to Buy and Sell Stock II

Link to Leetcode question1

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1

1
2
3
4
5

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2

1
2
3
4

Input: prices = [1,2,3,4,5]
Output: 4
Explanation**: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3

1
2
3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Solution

A detailed explaination of solution can be found here2.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution(object):
    def maxProfit(self, prices):
        stack = []
        buy = prices[0]
        sell = prices[0]

        def add(buy, sell):
            if len(stack) != 0:
                prv = stack[-1]
                if buy > prv[1]:
                    stack.pop()
                    stack.append([prv[0],sell])
                else:
                    stack.append([buy,sell])
                
            elif buy != sell:
                stack.append([buy,sell])

        for i in range(1, len(prices)):
            
            p = prices[i]
            if p < buy:
                if buy != sell:
                    add(buy, sell)
                    buy, sell = prices[i], prices[i]
                buy = p
                sell = p
                continue
            elif p > sell:
                sell = p
                continue
            elif buy != sell:
                add(buy, sell)
                buy, sell = prices[i], prices[i]
        
        if buy != sell:
            stack.append([buy,sell])
        
        profit = 0
        for deal in stack:
            profit += deal[1] - deal[0]
        
        return profit

1
2
3
4
5
6

class Solution(object):
    def maxProfit(self, prices):
        result = 0
        for i in range(1, len(prices)):
            result += max(prices[i] - prices[i - 1], 0)
        return result

Similar Questions

DiffSimilar QuestionsPythonJava
Medium309 Best Time to Buy and Sell Stock with Cooldown3  
Hard123 Best Time to Buy and Sell Stock III4  
Hard188 Best Time to Buy and Sell Stock IV5  

Jump Game

Link to Leetcode question6

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1

1
2
3

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2

1
2
3

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Solution

A detailed explaination of solution can be found here7.

Python

1
2
3
4
5
6
7
8
9

class Solution(object):
    def canJump(self, nums):
        last_pos = len(nums) - 1
        
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= last_pos:
                last_pos = i
        
        return last_pos == 0

Jump Game II

Link to Leetcode question8

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1

1
2
3

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2

1
2

Input: nums = [2,3,0,1,4]
Output: 2

Solution

A detailed explaination of solution can be found here9.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution(object):
    def jump(self, nums):
        if len(nums) == 1:
            return 0

        last_pos = len(nums) - 1
        stack = []
        
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= last_pos:
                stack.append(i)
        while len(stack) != 0:
            i = stack[-1]
            stack.pop()
            result = self.jump(nums[:i + 1])
            if result != -1:
                return result + 1
        
        return - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def jump(self, nums):
        if len(nums) == 1:
            return 0
        
        cur_distance = 0  # 当前覆盖最远距离下标
        ans = 0  # 记录走的最大步数
        next_distance = 0  # 下一步覆盖最远距离下标
        
        for i in range(len(nums)):
            next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖最远距离下标
            if i == cur_distance:  # 遇到当前覆盖最远距离下标
                ans += 1  # 需要走下一步
                cur_distance = next_distance  # 更新当前覆盖最远距离下标（相当于加油了）
                if next_distance >= len(nums) - 1:  # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束
                    break
        
        return ans

Similar Questions

DiffSimilar QuestionsPythonJava
Medium1306 Jump Game III8  
Medium1871 Jump Game VII10  

Maximize Sum Of Array After K Negations

Link to Leetcode question11

Given an integer array nums and an integer k, modify the array in the following way:

  • choose an index i and replace nums[i] with -nums[i].
  • You should apply this process exactly k times. You may choose the same index i multiple times.

Return the largest possible sum of the array after modifying it in this way.

Example 1

1
2
3

Input: nums = [4,2,3], k = 1
Output: 5
Explanation: Choose index 1 and nums becomes [4,-2,3].

Example 2

1
2
3

Input: nums = [3,-1,0,2], k = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3

1
2
3

Input: nums = [2,-3,-1,5,-4], k = 2
Output: 13
Explanation: Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

Solution

A detailed explaination of solution can be found here12.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def largestSumAfterKNegations(self, nums, k):
        nums.sort(key=lambda x: abs(x), reverse=True)

        for i in range(len(nums)):
            if nums[i] < 0:
                if k > 0:
                    nums[i] = - nums[i]
                    k -= 1
        
        if k % 2 == 1:
            nums[-1] = -nums[-1]
        
        return sum(nums)

Similar Questions

DiffSimilar QuestionsPythonJava
Medium2099 Find Subsequence of Length K With the Largest Sum13  

Reference

  1. Leetcode-122 Best Time to Buy and Sell Stock II: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/. ↩︎

  2. 代码随想录-买卖股票的最佳时机II: https://programmercarl.com/0122.买卖股票的最佳时机II.html. ↩︎

  3. Leetcode-309 Best Time to Buy and Sell Stock with Cooldown: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/. ↩︎

  4. Leetcode-123 Best Time to Buy and Sell Stock III: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/. ↩︎

  5. Leetcode-188 Best Time to Buy and Sell Stock IV: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/. ↩︎

  6. Leetcode-55 Jump Game: https://leetcode.com/problems/jump-game/description/. ↩︎

  7. 代码随想录-跳跃游戏: https://programmercarl.com/0055.跳跃游戏.html. ↩︎

  8. Leetcode-1306 Jump Game III: https://leetcode.com/problems/jump-game-iii/description/. ↩︎ ↩︎2

  9. 代码随想录-跳跃游戏II: https://programmercarl.com/0045.跳跃游戏II.html. ↩︎

  10. Leetcode-1871 Jump Game VII: https://leetcode.com/problems/jump-game-vii/description/. ↩︎

  11. Leetcode-1005 Maximize Sum Of Array After K Negations: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/description/. ↩︎

  12. 代码随想录-K次取反后最大化的数组和: https://programmercarl.com/1005.K次取反后最大化的数组和.html. ↩︎

  13. leetcode-2099 Find Subsequence of Length K With the Largest Sum: https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/description/. ↩︎

Data Structure and Algorithm, Leetcode, Greedy
greedy algorithm
This post is licensed under CC BY 4.0 by the author.