Skip to content

DP State Machine Basics

Table of Contents

3259. Maximum Energy Boost From Two Drinks

2222. Number of Ways to Select Buildings

1567. Maximum Length of Subarray With Positive Product

2708. Maximum Strength of a Group

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, backtracking, greedy, bit manipulation, sorting, enumeration

2708. Maximum Strength of a Group - Python Solution
from typing import List


# DP
def maxStrength(nums: List[int]) -> int:
    if not nums:
        return 0

    cur_min, cur_max = nums[0], nums[0]

    for i, num in enumerate(nums):
        if i == 0:
            continue

        temp_min = min(cur_min, num, num * cur_min, num * cur_max)
        temp_max = max(cur_max, num, num * cur_min, num * cur_max)
        cur_min, cur_max = temp_min, temp_max

    return cur_max


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |  DP        |  O(N)  |  O(1)   |
# |------------|--------|---------|


nums = [3, -1, -5, 2, 5, -9]
print(maxStrength(nums))  # 1350

2826. Sorting Three Groups

2786. Visit Array Positions to Maximize Score

1911. Maximum Alternating Subsequence Sum

376. Wiggle Subsequence

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, greedy

  • Return the length of the longest wiggle subsequence.
  • up[n] stores the length of the longest wiggle subsequence ending at n with a rising wiggle.
  • down[n] stores the length of the longest wiggle subsequence ending at n with a falling wiggle.
  • Initialize up[0] = 1 and down[0] = 1.
  • Example: nums = [1, 7, 4, 9, 2, 5]
nums[n] nums[n-1] up[n-1] down[n-1] up[n] down[n]
1 - - - 1 1
7 1 1 1 2 1
4 7 2 1 2 3
9 4 2 3 4 3
2 9 4 3 4 5
5 2 4 5 6 5
376. Wiggle Subsequence - Python Solution
from typing import List


# DP
def wiggleMaxLengthDP(nums: List[int]) -> int:
    if len(nums) <= 1:
        return len(nums)

    up = [0 for _ in range(len(nums))]
    down = [0 for _ in range(len(nums))]

    up[0], down[0] = 1, 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up[i] = down[i - 1] + 1
            down[i] = down[i - 1]
        elif nums[i] < nums[i - 1]:
            down[i] = up[i - 1] + 1
            up[i] = up[i - 1]
        else:
            up[i] = up[i - 1]
            down[i] = down[i - 1]

    return max(up[-1], down[-1])


# Greedy
def wiggleMaxLengthGreedy(nums: List[int]) -> int:
    if len(nums) < 2:
        return len(nums)

    prev_diff = nums[1] - nums[0]
    count = 2 if prev_diff != 0 else 1

    for i in range(2, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and prev_diff <= 0) or (diff < 0 and prev_diff >= 0):
            count += 1
            prev_diff = diff

    return count


# |-------------|-----------------|--------------|
# |  Approach   |      Time       |    Space     |
# |-------------|-----------------|--------------|
# |    DP       |      O(n)       |     O(n)     |
# |  Greedy     |      O(n)       |     O(1)     |
# |-------------|-----------------|--------------|

nums = [1, 7, 4, 9, 2, 5]
print(wiggleMaxLengthDP(nums))  # 6
print(wiggleMaxLengthGreedy(nums))  # 6

1186. Maximum Subarray Sum with One Deletion

1186. Maximum Subarray Sum with One Deletion - Python Solution
from typing import List


# DP - Kadane
def maximumSum(arr: List[int]) -> int:
    dp0 = arr[0]
    dp1 = 0
    maxSum = dp0

    for i in range(1, len(arr)):
        dp1 = max(dp1 + arr[i], dp0)  # delete previous element or not
        dp0 = max(dp0, 0) + arr[i]  # delete current element or not
        maxSum = max(maxSum, dp0, dp1)  # update result

    return maxSum


arr = [1, -2, 0, 3]
print(maximumSum(arr))  # 4

Comments