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

2919. Minimum Increment Operations to Make Array Beautiful

801. Minimum Swaps To Make Sequences Increasing

3434. Maximum Frequency After Subarray Operation

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, dynamic programming, greedy, prefix sum

1955. Count Number of Special Subsequences

3068. Find the Maximum Sum of Node Values

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, dynamic programming, greedy, bit manipulation, tree, sorting

2272. Substring With Largest Variance

2272. Substring With Largest Variance - Python Solution
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

Comments