Problem Link - Brackets
Problem Statement
There are k types of brackets each with its own opening bracket and closing bracket. We assume that the first pair is denoted by the numbers 1 and k+1, the second by 2 and k+2 and so on. Thus the opening brackets are denoted by 1,2, ... 2 \times k , and the corresponding closing brackets are denoted by k+1, k+2,..., 2 \times k respectively.
Some sequences with elements from 1,2, ... 2 \times k form well-bracketed sequences while others don’t. A sequence is well-bracketed, if we can match or pair up opening brackets and closing brackets of the same type in such a way that the following holds:
1) every bracket is paired up
2) in each matched pair, the opening bracket occurs before the closing bracket
3) for a matched pair, any other matched pair lies either completely between them or outside them
Approach
To solve the problem, a dynamic programming approach is used to find the maximum value of a well-bracketed sequence. A 2D DP table, dp, is used where dp[l][r] stores the maximum value of the sequence from index l to r. The table is filled in reverse order for the left index (l) to ensure dependencies are resolved before processing a pair. For every range [l, r], if the brackets at l and r form a valid pair (i.e., a[l] + k == a[r]), their values contribute to the result, and the sum of the sequence values v[l] + v[r] is considered. Additionally, all partitions of the range are explored to find the optimal way to divide the range and compute the best result using previously computed DP values.
Time Complexity
The time complexity is O(n^3) because there are O(n^2) DP states and computing each state requires traversing the range between l and r.
Space Complexity
The space complexity is O(n^2) due to the 2D DP table used for storing results of subproblems.