Painting the Array I (Codeforces 1479B1)
Tags: Greedy, data structures

The only difference between the two versions is that this version asks the maximal possible answer.Homer likes arrays a lot. Today he is painting an array $$$a_1, a_2, \dots, a_n$$$ with two kinds of colors, white and black. A painting assignment for $$$a_1, a_2, \dots, a_n$$$ is described by an array $$$b_1, b_2, \dots, b_n$$$ that $$$b_i$$$ indicates the color of $$$a_i$$$ ($$$0$$$ for white and $$$1$$$ for black).According to a painting assignment $$$b_1, b_2, \dots, b_n$$$, the array $$$a$$$ is split into two new arrays $$$a^{(0)}$$$ and $$$a^{(1)}$$$, where $$$a^{(0)}$$$ is the sub-sequence of all white elements in $$$a$$$ and $$$a^{(1)}$$$ is the sub-sequence of all black elements in $$$a$$$. For example, if $$$a = [1,2,3,4,5,6]$$$ and $$$b = [0,1,0,1,0,0]$$$, then $$$a^{(0)} = [1,3,5,6]$$$ and $$$a^{(1)} = [2,4]$$$.The number of segments in an array $$$c_1, c_2, \dots, c_k$$$, denoted $$$\mathit{seg}(c)$$$, is the number of elements if we merge all adjacent elements with the same value in $$$c$$$. For example, the number of segments in $$$[1,1,2,2,3,3,3,2]$$$ is $$$4$$$, because the array will become $$$[1,2,3,2]$$$ after merging adjacent elements with the same value. Especially, the number of segments in an empty array is $$$0$$$.Homer wants to find a painting assignment $$$b$$$, according to which the number of segments in both $$$a^{(0)}$$$ and $$$a^{(1)}$$$, i.e. $$$\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$$$, is as large as possible. Find this number.

Input: The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Output: Output a single integer, indicating the maximal possible total number of segments.

Note: In the first example, we can choose $$$a^{(0)} = [1,2,3,3]$$$, $$$a^{(1)} = [1,2,3]$$$ and $$$\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 3$$$. So the answer is $$$3+3 = 6$$$.In the second example, we can choose $$$a^{(0)} = [1,2,3,4,5,6,7]$$$ and $$$a^{(1)}$$$ is empty. We can see that $$$\mathit{seg}(a^{(0)}) = 7$$$ and $$$\mathit{seg}(a^{(1)}) = 0$$$. So the answer is $$$7+0 = 7$$$.

Sample Inputs:
7
1 1 2 2 3 3 3

7
1 2 3 4 5 6 7

Sample Outputs:
6

7

Solution (Python):
import sys
input = sys.stdin.readline
flush = sys.stdout.flush

def stupid(pos, p1, p2, c1, c2, a):
    if pos == len(a):
        return p1 + p2
    return max(stupid(pos + 1, a[pos], p2, c1 + int(p1 != a[pos]), c2, a), stupid(pos + 1, p1, a[pos], c1, c2 + int(p2 != a[pos]), a))

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    p = -1
    p1 = -1
    pos1 = -1
    c1 = 0
    c2 = 0
    j = 0
    for i in a:
        if i != p:
            p = i
            c1 += 1
        else:
            if i != p1:
                c2 += 1
            else:
                for k in range(pos1 + 1, j):
                    if a[k] != p1 and a[k - 1] != a[k + 1]:
                        c2 += 1
                        break
            p1 = i
            pos1 = j
        j += 1
    print(c1 + c2)
solve()

Solution (Python):
import sys

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    last_pair = -1
    res = 0
    lhs = (0, a[0])
    for (key, value) in enumerate(a):
        if value != lhs[1]:
            if lhs[1] != last_pair and value != last_pair:
                last_pair = -1
            if key - lhs[0] > 1:
                res += 1
                if lhs[1] == last_pair:
                    res -= 1
                last_pair = lhs[1]
            res += 1
            lhs = (key, value)
    res += 1
    if n - lhs[0] > 1:
        res += 1
        if lhs[1] == last_pair:
            res -= 1
    print(res)
    return
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
getint = lambda : int(input())
getints = lambda : [int(a) for a in input().split()]

def solve():
    n = getint()
    values = getints()
    pos = [-1 for i in range(n + 1)]
    next = [n for i in range(n)]
    for i in range(n):
        if pos[values[i]] != -1:
            next[pos[values[i]]] = i
        pos[values[i]] = i
    one = -1
    two = -1
    onei = -1
    twoi = -1
    segments = 0
    for i in range(n):
        v = values[i]
        if v == two:
            segments += 1 if v != one else 0
            one = v
            onei = i
        elif v == one:
            segments += 1
            two = v
            twoi = i
        elif next[onei] > next[twoi]:
            segments += 1
            two = v
            twoi = i
        else:
            segments += 1
            one = v
            onei = i
    print(segments)
if __name__ == '__main__':
    solve()