Skip to content

DP State Machine Advanced

Table of Contents

1262. Greatest Sum Divisible by Three

1363. Largest Multiple of Three

2771. Longest Non-decreasing Subarray From Two Arrays

1594. Maximum Non Negative Product in a Matrix

3196. Maximize Total Cost of Alternating Subarrays

935. Knight Dialer

1537. Get the Maximum Score

  • LeetCode | 力扣

  • Tags: Array, Two Pointers, Dynamic Programming, Greedy

2919. Minimum Increment Operations to Make Array Beautiful

801. Minimum Swaps To Make Sequences Increasing

3434. Maximum Frequency After Subarray Operation

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Dynamic Programming, Greedy, Prefix Sum

1955. Count Number of Special Subsequences

3068. Find the Maximum Sum of Node Values

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Greedy, Bit Manipulation, Tree, Sorting

2272. Substring With Largest Variance

from itertools import permutations
from math import inf
from string import ascii_lowercase


# DP State Machine
def largestVariance(s: str) -> int:
    res = 0

    for a, b in permutations(ascii_lowercase, 2):
        f0, f1 = 0, -inf
        for ch in s:
            if ch == a:
                f0 = max(f0, 0) + 1
                f1 += 1
            elif ch == b:
                f1 = f0 = max(f0, 0) - 1

            res = max(res, f1)
    return res


if __name__ == "__main__":
    s = "aababbb"
    print(largestVariance(s))  # 3

276. Paint Fence 👑

1746. Maximum Subarray Sum After One Operation 👑

2036. Maximum Alternating Subarray Sum 👑

2361. Minimum Costs Using the Train Line 👑

3269. Constructing Two Increasing Arrays 👑