Tenzing and Balls (Codeforces 1842C)
Tags: DP, dp

Enjoy erasing Tenzing, identified as Accepted!Tenzing has $$$n$$$ balls arranged in a line. The color of the $$$i$$$-th ball from the left is $$$a_i$$$.Tenzing can do the following operation any number of times:  select $$$i$$$ and $$$j$$$ such that $$$1\leq i < j \leq |a|$$$ and $$$a_i=a_j$$$,  remove $$$a_i,a_{i+1},\ldots,a_j$$$ from the array (and decrease the indices of all elements to the right of $$$a_j$$$ by $$$j-i+1$$$). Tenzing wants to know the maximum number of balls he can remove.

Input: Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10^3$$$) — the number of test cases. The description of test cases follows.The first line contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the number of balls.The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq n$$$) — the color of the balls.It is guaranteed that sum of $$$n$$$ of all test cases will not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output the maximum number of balls Tenzing can remove.

Note: In the first example, Tenzing will choose $$$i=2$$$ and $$$j=3$$$ in the first operation so that $$$a=[1,3,3]$$$. Then Tenzing will choose $$$i=2$$$ and $$$j=3$$$ again in the second operation so that $$$a=[1]$$$. So Tenzing can remove $$$4$$$ balls in total.In the second example, Tenzing will choose $$$i=1$$$ and $$$j=3$$$ in the first and only operation so that $$$a=[2]$$$. So Tenzing can remove $$$3$$$ balls in total.

Sample Inputs:
2
5
1 2 2 3 3
4
1 2 1 2

Sample Outputs:
4
3

Solution (Python):
def solve(a, n):
    occur = [-1] * (n + 1)
    dp = [0] * n
    change = -1
    changes = [False] * n
    for i in range(n):
        if i > 0:
            dp[i] = dp[i - 1]
        if occur[a[i]] != -1:
            if change <= occur[a[i]]:
                dp[i] += i - occur[a[i]]
                change = i
                changes[i] = True
                if not changes[occur[a[i]]]:
                    dp[i] += 1
            else:
                tmp = dp[occur[a[i]]] + i - occur[a[i]]
                if not changes[occur[a[i]]]:
                    tmp += 1
                if tmp > dp[i]:
                    dp[i] = tmp
                    change = i
                    changes[i] = True
        occur[a[i]] = i
    return dp[-1]

def main():
    t = int(input())
    for tests in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        print(solve(a, n))
main()

Solution (Python):
def solve():
    n = int(input())
    f = [0] * (n + 1)
    g = [-n] * (n + 1)
    a = list(map(int, input().split()))
    for i in range(1, n + 1):
        x = a[i - 1]
        f[i] = max(f[i - 1], g[x] + i)
        g[x] = max(g[x], f[i - 1] - i + 1)
    print(f[n])
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import math
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    dp = [0] * n
    fd = [n + 1] * (n + 1)
    for i in range(n):
        if i == 0:
            dp[0] = 1
            fd[arr[i]] = 0
        else:
            dp[i] = min(dp[i - 1] + 1, fd[arr[i]])
            fd[arr[i]] = min(fd[arr[i]], dp[i - 1])
    print(n - dp[-1])