Problem:

Given an array A of size N

We need to partition it into non-overlapping subarrays (continuous segments)

For each segment: MEX = smallest non-negative integer not present

Score = sum of MEX of all segments

Goal: Maximize total score

example

1. a= 0,2,1,1 ans= 3 (we can divide it into {0,2,1},{1} whose MEX are 3 and 0 respectively)

2.a= 0,2,1,1,0 ans= 5 (we can divide it into {0,2,1},{1,0} whose MEX are 3 and 2 respectively)

What I tried-

1. DP, 1 state, but it had a for loop inside it that was running from i to n. O(n^2). This caused TLE ofcourse.
2. DP, same as above, but I called rec() it whenever I encountered 0;

mex=0; for(i to n) keeping mex updated if(arr[i]==0) ans=max(ans, mex+rec(i))

return max(ans,mex)

This ran few cases for the dry run, but for hidden cases it wasn't running. the reason i thought of calling rec() because the partition need an element 0 for MEX to calculate

1. greedy, but was couldn't find the right approach/ direction for greedy. I was again cutting whenever i was finding 0 but wasn't good solution.

Doubt:

• Is there a correct greedy strategy?
• Or is there a way to optimize DP?
• What observation am I missing?

Thanks.