Let an array of size n , 1 \leq n \leq 30 is made by permuting the set \{1,2,3 \cdots n\}.
Now I have given some k numbers from the above set , k \leq n numbers which are prefix of the permutation array and now the array is formed by
a_1, a _2, \cdots a_k fixed prefix and remaining permutation of n - k elements a_{k+1}, a_{k+2} \cdots a_n.
Let the sum s is defined by \sum_{i = 1}^n max(0, i - a_i).
How to find all possible values of sum.
Since the first k values are given fixed then \sum_{i = 1}^k max(0, i - a_i) can be found easily but how to find all possible values of \sum_{i = k+1}^n max(0, i - a_i).
For example n = 5 , k = 2
prefix arr = 2 \> 1
\sum_{i = 1}^2 max(0, i - a_i) = max(0, 1 -2) + max (0, 2 - 1) = 0 + 1 = 1
There are 3! = 6 array possible for above prefix.
2 \>1 \>3 \> 4 \>5
Sum = 1 + max(0, 3 - 3) + max(0, 4 - 4) + max(0, 5 - 5) = 0 + 1 + 0 + 0 + 0 = 1
2 \>1 \>4 \> 3 \>5
Sum = 1 + max(0, 3 - 4) + max(0, 4 - 3) + max(0, 5 - 5) = 1 + 0 + 1 + 0 = 2
2 \>1 \>4 \> 5 \>3
Sum = 1 + max(0, 3 - 4) + max(0, 4 - 5) + max(0, 5 - 3) = 1 + 0 + 0 + 2 = 2
2 \>1 \>3 \> 5 \>4
Sum = 1+ max(0, 3 - 3) + max(0, 4 - 5) + max(0, 5 - 4) = 1 + 0 + 0 + 1 = 2
2 \>1 \>5 \> 3 \>4
Sum = 1 + max(0, 3 - 5) + max(0, 4 - 3) + max(0, 5 - 4) = 1 + 0 + 1 + 1 = 3
2 \>1 \>5 \> 4 \>3
Sum = 1 + max(0, 3 - 5) + max(0, 4 - 4) + max(0, 5 - 3) = 1 + 0 + 0 + 2 = 3
so all possible sum = \{ 1, 2 , 3 \}
Finding all permutation of the array is not possible because of very high time complexity. Please help.