In this problem, we are asked to partition an array into two arrays A and B, and maximize seg(A) + seg(B), where seg(array) is the number of occurrences of i such that a[i] != a[i-1], plus 1. It is also the number of segments of the array, where each element on the segment has the same value, and the segment cannot be made larger. So for an array like 1,1,2,2,3,1 the "seg" value of the array is 4.

My approach for this is as follows: Since the original array is composed of these segments as well, we can look at each segment separately. For each segment, I think we can just let the first element of the segment be part of array A, and the rest to be part of array B. Then, we just calculate seg(A) and seg(B) and add them to get the result.

My logic for why this works is that if we change this construction by moving one element of array A to array B, the answer won't change. Let's say, for example, the original array looks like this:

a,a,...,a,a,b,b,b,..,b,b,b,c,c,c,...,c,c,c, where a, b, c are some random integers.

According to our construction,
A = a,b,c.
B = a,a,a, ...,a,b,b,...,b,c,c,c, ...,c.

If we move an element from B to A, then A just gets one more of a,b, or c and the answer is still the same. If we move an element from A to B, the same thing happens.

I am pretty convinced that my approach is correct, but my approach doesn't work for test case 6 of this problem (you can view my submission here). Does anyone know an example or reason why my logic fails? Thank you!