DP Fenwick Tree Segment Tree

Table of Contents

• 1626. Best Team With No Conflicts (Medium)
• 2407. Longest Increasing Subsequence II (Hard)
• 2770. Maximum Number of Jumps to Reach the Last Index (Medium)
• 2926. Maximum Balanced Subsequence Sum (Hard)
• 2916. Subarrays Distinct Element Sum of Squares II (Hard)
• 3410. Maximize Subarray Sum After Removing All Occurrences of One Element (Hard)

1626. Best Team With No Conflicts

• LeetCode | LeetCode CH (Medium)

• Tags: array, dynamic programming, sorting

1626. Best Team With No Conflicts - Python Solution

from typing import List


# DP - LIS
def bestTeamScore(scores: List[int], ages: List[int]) -> int:
    n = len(scores)
    pairs = sorted(zip(scores, ages))  # sort
    dp = [0 for _ in range(n)]

    # LIS
    for i in range(n):
        for j in range(i):
            if pairs[i][1] >= pairs[j][1]:
                dp[i] = max(dp[i], dp[j])
        dp[i] += pairs[i][0]

    return max(dp)


if __name__ == "__main__":
    assert bestTeamScore([1, 3, 5, 10, 15], [1, 2, 3, 4, 5]) == 34
    assert bestTeamScore([4, 5, 6, 5], [2, 1, 2, 1]) == 16

2407. Longest Increasing Subsequence II

• LeetCode | LeetCode CH (Hard)

• Tags: array, divide and conquer, dynamic programming, binary indexed tree, segment tree, queue, monotonic queue

2770. Maximum Number of Jumps to Reach the Last Index

• LeetCode | LeetCode CH (Medium)

• Tags: array, dynamic programming

2926. Maximum Balanced Subsequence Sum

• LeetCode | LeetCode CH (Hard)

• Tags: array, binary search, dynamic programming, binary indexed tree, segment tree

2916. Subarrays Distinct Element Sum of Squares II

• LeetCode | LeetCode CH (Hard)

• Tags: array, dynamic programming, binary indexed tree, segment tree

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

• LeetCode | LeetCode CH (Hard)

• Tags: array, dynamic programming, segment tree

Comments