Skip to content

DP Prefix and Suffix Decomposition

Table of Contents

724. Find Pivot Index

1991. Find the Middle Index in Array

2270. Number of Ways to Split Array

2256. Minimum Average Difference

1422. Maximum Score After Splitting a String

1493. Longest Subarray of 1's After Deleting One Element

from typing import List


# Sliding Window Variable Max
def longestSubarray(nums: List[int]) -> int:
    zeroCount = 0
    res = 0
    left = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeroCount += 1

        while zeroCount > 1:
            if nums[left] == 0:
                zeroCount -= 1
            left += 1

        res = max(res, right - left)

    return res


nums = [1, 1, 0, 1]
print(longestSubarray(nums))  # 3

845. Longest Mountain in Array

  • LeetCode | 力扣

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

from typing import List


# Left Right Pointers
def longestMountain(arr: List[int]) -> int:
    n = len(arr)
    res = 0
    left = 0

    while left < n:
        right = left

        if right < n - 1 and arr[right] < arr[right + 1]:
            while right < n - 1 and arr[right] < arr[right + 1]:
                right += 1

            if right < n - 1 and arr[right] > arr[right + 1]:
                while right < n - 1 and arr[right] > arr[right + 1]:
                    right += 1
                res = max(res, right - left + 1)

        left = max(right, left + 1)

    return res


arr = [2, 1, 4, 7, 3, 2, 5]
print(longestMountain(arr))  # 5

2012. Sum of Beauty in the Array

from typing import List


# DP Prefix and Suffix Decomposition
def sumOfBeauties(nums: List[int]) -> int:
    n = len(nums)
    suf_min = [0] * n
    suf_min[n - 1] = nums[n - 1]
    for i in range(n - 2, 1, -1):
        suf_min[i] = min(suf_min[i + 1], nums[i])

    res = 0
    pre_max = nums[0]
    for i in range(1, n - 1):
        x = nums[i]
        if pre_max < x < suf_min[i + 1]:
            res += 2
        elif nums[i - 1] < x < nums[i + 1]:
            res += 1
        pre_max = max(pre_max, x)

    return res


nums = [2, 4, 6, 4, 5]
print(sumOfBeauties(nums))  # 1

2909. Minimum Sum of Mountain Triplets II

2483. Minimum Penalty for a Shop

1525. Number of Good Ways to Split a String

  • LeetCode | 力扣

  • Tags: Hash Table, String, Dynamic Programming, Bit Manipulation

3354. Make Array Elements Equal to Zero

2874. Maximum Value of an Ordered Triplet II

from typing import List


def maximumTripletValue(nums: List[int]) -> int:
    res = 0
    max_diff = 0
    max_prev = 0

    for num in nums:
        res = max(res, max_diff * num)
        max_diff = max(max_diff, max_prev - num)
        max_prev = max(max_prev, num)

    return res


if __name__ == "__main__":
    nums = [12, 6, 1, 2, 7]
    print(maximumTripletValue(nums))  # 77

123. Best Time to Buy and Sell Stock III

from typing import List


# 1. DP
def maxProfitDP1(prices: List[int]) -> int:
    n = len(prices)
    if n <= 1:
        return 0

    dp = [[0] * 5 for _ in range(n)]

    dp[0][0] = 0  # no transaction
    dp[0][1] = -prices[0]  # buy 1
    dp[0][2] = 0  # sell 1
    dp[0][3] = -prices[0]  # buy 2
    dp[0][4] = 0  # sell 2

    for i in range(1, n):
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = max(dp[i - 1][1], -prices[i])
        dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
        dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
        dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

    return dp[-1][4]


# 2. DP - Optimized
def maxProfitDP2(prices: List[int]) -> int:
    b1, b2 = float("inf"), float("inf")
    s1, s2 = 0, 0

    for price in prices:
        b1 = min(b1, price)
        s1 = max(s1, price - b1)
        b2 = min(b2, price - s1)
        s2 = max(s2, price - b2)

    return s2


prices = [3, 3, 5, 0, 0, 3, 1, 4]
print(maxProfitDP1(prices))  # 6
print(maxProfitDP2(prices))  # 6

2222. Number of Ways to Select Buildings

1031. Maximum Sum of Two Non-Overlapping Subarrays

689. Maximum Sum of 3 Non-Overlapping Subarrays

2420. Find All Good Indices

2100. Find Good Days to Rob the Bank

926. Flip String to Monotone Increasing

334. Increasing Triplet Subsequence

2712. Minimum Cost to Make All Characters Equal

def minimumCost(s: str) -> int:
    n = len(s)
    res = 0
    for i in range(1, n):
        if s[i - 1] != s[i]:
            res += min(i, n - i)

    return res


if __name__ == "__main__":
    s = "0011"
    print(minimumCost(s))  # 2

1653. Minimum Deletions to Make String Balanced

1186. Maximum Subarray Sum with One Deletion

"""
- [灵神：教你一步步思考动态规划 - 从记忆化搜索到递推](https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/solutions/2321829/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-hzz6))
"""

from functools import cache
from math import inf
from typing import List


# DP - Kadane
def maximumSum(arr: List[int]) -> int:
    dp0 = arr[0]
    dp1 = 0
    res = 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
        res = max(res, dp0, dp1)  # update result

    return res


# DP - Memoization
def maximumSumMemo(arr: List[int]) -> int:
    @cache
    def dfs(i: int, j: int) -> int:
        if i < 0:
            return -inf
        if j == 0:
            return max(dfs(i - 1, 0), 0) + arr[i]
        return max(dfs(i - 1, 1) + arr[i], dfs(i - 1, 0))

    return max(max(dfs(i, 0), dfs(i, 1)) for i in range(len(arr)))


if __name__ == "__main__":
    arr = [1, -2, 0, 3]
    assert maximumSum(arr) == 4
    assert maximumSumMemo(arr) == 4

42. Trapping Rain Water

  • LeetCode | 力扣

  • Tags: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

"""
- ![42](../../assets/0042.png)

<iframe width="560" height="315" src="https://www.youtube.com/embed/ZI2z5pq0TqA?si=OEYg01dbmzvmtIwZ" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>

| Approach   | Time | Space |
| ---------- | ---- | ----- |
| DP         | O(N) | O(N)  |
| Left Right | O(N) | O(1)  |
| Monotonic  | O(N) | O(N)  |
"""

from typing import List


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

    n = len(height)
    maxLeft, maxRight = [0 for _ in range(n)], [0 for _ in range(n)]

    for i in range(1, n):
        maxLeft[i] = max(maxLeft[i - 1], height[i - 1])

    for i in range(n - 2, -1, -1):
        maxRight[i] = max(maxRight[i + 1], height[i + 1])

    res = 0
    for i in range(n):
        res += max(0, min(maxLeft[i], maxRight[i]) - height[i])

    return res


# Left Right Pointers
def trapLR(height: List[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    maxL, maxR = height[left], height[right]
    res = 0

    while left < right:
        if maxL < maxR:
            left += 1
            maxL = max(maxL, height[left])
            res += maxL - height[left]
        else:
            right -= 1
            maxR = max(maxR, height[right])
            res += maxR - height[right]

    return res


# Monotonic Stack
def trapStack(height: List[int]) -> int:
    stack = []
    total = 0

    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[top]
            total += distance * bounded_height
        stack.append(i)

    return total


height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trapDP(height))  # 6
print(trapLR(height))  # 6
print(trapStack(height))  # 6

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        if (height.empty())
            return 0;

        int res = 0;
        int left = 0, right = height.size() - 1;
        int maxL = height[left], maxR = height[right];

        while (left < right)
        {
            if (maxL < maxR)
            {
                left++;
                maxL = max(maxL, height[left]);
                res += maxL - height[left];
            }
            else
            {
                right--;
                maxR = max(maxR, height[right]);
                res += maxR - height[right];
            }
        }
        return res;
    }
};

int main()
{
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    Solution solution;
    cout << solution.trap(height) << endl;
    return 0;
}

2711. Difference of Number of Distinct Values on Diagonals

from typing import List


def differenceOfDistinctValues(grid: List[List[int]]) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    res = [[0] * n for _ in range(m)]
    st = set()

    for k in range(1, m + n):
        min_j = max(n - k, 0)
        max_j = min(m + n - 1 - k, n - 1)

        st.clear()
        for j in range(min_j, max_j + 1):
            i = k + j - n
            res[i][j] = len(st)
            st.add(grid[i][j])

        st.clear()
        for j in range(max_j, min_j - 1, -1):
            i = k + j - n
            res[i][j] = abs(res[i][j] - len(st))
            st.add(grid[i][j])

    return res


if __name__ == "__main__":
    grid = [[1, 2, 3], [3, 1, 5], [3, 2, 1]]
    print(differenceOfDistinctValues(grid))
    # [[1, 1, 0], [1, 0, 1], [0, 1, 1]]

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

  • LeetCode | 力扣

  • Tags: Array, Hash Table, Binary Search, Dynamic Programming, Sliding Window

2680. Maximum OR

from typing import List


# Greedy
def maximumOr(nums: List[int], k: int) -> int:
    """Maximum OR of Array After k Operations

    Args:
        nums (List[int]): provided list of integers
        k (int): number of operations

    Returns:
        int: maximum OR of array after k operations
    """
    n = len(nums)
    suffix = [0 for _ in range(n)]

    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] | nums[i + 1]

    res, pre = 0, 0
    for num, suf in zip(nums, suffix):
        res = max(res, pre | (num << k) | suf)
        pre |= num

    return res


if __name__ == "__main__":
    print(maximumOr(nums=[8, 1, 2], k=2))  # 35

1671. Minimum Number of Removals to Make Mountain Array

  • LeetCode | 力扣

  • Tags: Array, Binary Search, Dynamic Programming, Greedy

from typing import List


# DP - LIS
def minimumMountainRemovals(nums: List[int]) -> int:
    n = len(nums)
    lis = [1 for _ in range(n)]
    lds = [1 for _ in range(n)]

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    for i in range(n - 2, -1, -1):
        for j in range(n - 1, i, -1):
            if nums[i] > nums[j]:
                lds[i] = max(lds[i], lds[j] + 1)

    maxLen = 0
    for i in range(1, n - 1):
        if lis[i] > 1 and lds[i] > 1:
            maxLen = max(maxLen, lis[i] + lds[i] - 1)

    return n - maxLen


nums = [2, 1, 1, 5, 6, 2, 3, 1]
print(minimumMountainRemovals(nums))  # 3

1888. Minimum Number of Flips to Make the Binary String Alternating

  • LeetCode | 力扣

  • Tags: String, Dynamic Programming, Greedy, Sliding Window

238. Product of Array Except Self

"""
-   Classic **Prefix Sum** problem
-   Return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

| Approach           | Time | Space |
| ------------------ | ---- | ----- |
| Prefix             | O(n) | O(n)  |
| Prefix (Optimized) | O(n) | O(1)  |
"""

from typing import List


# Prefix
def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    prefix = [1 for _ in range(n)]
    suffix = [1 for _ in range(n)]

    for i in range(1, n):
        prefix[i] = nums[i - 1] * prefix[i - 1]

    for i in range(n - 2, -1, -1):
        suffix[i] = nums[i + 1] * suffix[i + 1]

    result = [i * j for i, j in zip(prefix, suffix)]

    return result


# Prefix (Optimized)
def productExceptSelfOptimized(nums: List[int]) -> List[int]:
    n = len(nums)
    result = [1 for _ in range(n)]

    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result


print(productExceptSelf([1, 2, 3, 4]))
# [24, 12, 8, 6]
print(productExceptSelfOptimized([1, 2, 3, 4]))
# [24, 12, 8, 6]

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
   public:
    vector<int> productExceptSelf(vector<int> &nums) {
        int n = nums.size();
        vector<int> prefix(n, 1);
        vector<int> suffix(n, 1);
        vector<int> res(n, 1);

        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            res[i] = prefix[i] * suffix[i];
        }
        return res;
    }
};

int main() {
    vector<int> nums = {1, 2, 3, 4};
    Solution obj;
    vector<int> result = obj.productExceptSelf(nums);
    assert(result == vector<int>({24, 12, 8, 6}));
    return 0;
}

2906. Construct Product Matrix

3334. Find the Maximum Factor Score of Array

2167. Minimum Time to Remove All Cars Containing Illegal Goods

2484. Count Palindromic Subsequences

2163. Minimum Difference in Sums After Removal of Elements

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Heap Priority Queue

2565. Subsequence With the Minimum Score

1995. Count Special Quadruplets

2552. Count Increasing Quadruplets

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Binary Indexed Tree, Enumeration, Prefix Sum

from typing import List


# DP
def countQuadruplets(nums: List[int]) -> int:
    n = len(nums)
    great = [[0] * (n + 1) for _ in range(n)]
    less = [0 for _ in range(n + 1)]

    for k in range(n - 2, 1, -1):
        great[k] = great[k + 1].copy()
        for x in range(1, nums[k + 1]):
            great[k][x] += 1

    ans = 0

    for j in range(1, n - 1):
        for x in range(nums[j - 1] + 1, n + 1):
            less[x] += 1
        for k in range(j + 1, n - 1):
            if nums[j] > nums[k]:
                ans += less[nums[k]] * great[k][nums[j]]
    return ans


nums = [1, 3, 2, 4, 5]
print(countQuadruplets(nums))  # 2

3302. Find the Lexicographically Smallest Valid Sequence

  • LeetCode | 力扣

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

3404. Count Special Subsequences

3303. Find the Occurrence of First Almost Equal Substring

3287. Find the Maximum Sequence Value of Array

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Bit Manipulation

3257. Maximum Value Sum by Placing Three Rooks II

  • LeetCode | 力扣

  • Tags: Array, Dynamic Programming, Matrix, Enumeration

3410. Maximize Subarray Sum After Removing All Occurrences of One Element

3003. Maximize the Number of Partitions After Operations

  • LeetCode | 力扣

  • Tags: String, Dynamic Programming, Bit Manipulation, Bitmask

487. Max Consecutive Ones II

1746. Maximum Subarray Sum After One Operation

Comments