Painting the Array I (Codeforces 1480D1)
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

def rl(proc=None):
    if proc is not None:
        return proc(sys.stdin.readline())
    else:
        return sys.stdin.readline().rstrip()

def srl(proc=None):
    if proc is not None:
        return list(map(proc, rl().split()))
    else:
        return rl().split()

def good(r, v):
    return any((r[i] != v for i in range(1, len(r), 2)))

def main():
    rl()
    A = srl(int)
    v = A[0]
    c = 0
    ret = 0
    r = []
    last_bulk = -1
    A.append(0)
    for x in A:
        if x == v:
            c += 1
        else:
            if c == 1:
                r.append(v)
            else:
                if v != last_bulk:
                    ret += len(r) + 2
                    last_bulk = v
                elif good(r, v):
                    ret += len(r) + 2
                else:
                    ret += len(r) + 1
                r = []
            v = x
            c = 1
    assert c == 1
    assert v == 0
    ret += len(r)
    print(ret)
if __name__ == '__main__':
    main()

Solution (Python):
def painting_the_array_i(array):
    count = 0
    last1 = None
    last2 = None
    buffer = None
    buffer_count = 0
    for i in array:
        if last1 is None or (i != last1 and last2 is None):
            last1 = i
            count += 1
        elif last2 is None:
            last2 = i
            count += 1
        elif last1 == last2:
            if i != last1:
                count += 1
            last1 = i
        elif i == last1 and buffer is None:
            last2 = i
            count += 1
        elif i == last2 and buffer is None:
            last1 = i
            count += 1
        elif i == buffer:
            last1 = last2 = i
            count += buffer_count
            count += 1
            buffer = None
            buffer_count = 0
        else:
            buffer = i
            buffer_count += 1
    return count + buffer_count
if __name__ == '__main__':
    n = int(input())
    array = [int(i) for i in input().split()]
    print(painting_the_array_i(array))

Solution (Python):
from array import array

def solve(n, D):
    a = None
    b = None
    a_cnt = 0
    b_cnt = 0
    for (i, d) in enumerate(D):
        if a != d:
            if i < n - 1 and b == D[i + 1]:
                b_cnt += 1
                b = d
                continue
            a_cnt += 1
            a = d
            continue
        if b != d:
            b_cnt += 1
            b = d
    return a_cnt + b_cnt

def main():
    ans = []
    n = int(input())
    D = array('i', list(map(int, input().split(' '))))
    ans.append(solve(n, D))
    for a in ans:
        print(a)
if __name__ == '__main__':
    main()