You are given an array A, of size N, containing numbers from 0-N. For each sub-array starting from 0th index, lets say Si, we say Bi is the smallest non negative number that is not present in Si.

We need to find the maximum possible sum of all Bi of this array.

We can rearrange the array to obtain the maximum sum.

For example:

A = 1, 2, 0 , N = 3

then lets say we rearranged it as A= 0, 1, 2

S1 = 0, B1= 1

S2 = 0,1 B2= 2

S3 = 0,1,2 B3= 3

Hence the sum is 6

Whatever examples I have tried, I have seen that sorted array will give the maximum sum. Am I correct or missing something here.

Please help to find the correct logic for this problem. I am not looking for optimal solution but just the correct logic.

CodePudding user response：

Yes, sorting the array maximizes the sum of