Recently I came across such a question: You have to divide an array into k segments, and the resultant score of each segment is the number of pairs (i,j) such that i<j and a[i]>a[j]. For example, the score of [9,1,7,3,2] will be 7 since the following pairs can be formed: {9,1},{9,7},{9,3},{9,2},{7,3},{7,2},{3,2}. Now our task is to maximize the sum of scores of the resultant segments. The k segments can be formed only using continuous elements of the array. The constraints are:`1<=a[i]<=10**6`

`1<=n<=500`

`1<=k<=n`

I was thinking of a dp solution to this, where dp[i][j][len] stores the answer we can get after we reach the ith index, which belongs to the jth group of length len. Hence I declared an array dp[505][505][505]. The base case would be simply the following: And at each element we make the choice of ending a group or not

```
if(idx==n)
{
if(grp==k-1)//since we need k groups so this is the first and last element of the kth group
return 0;
if(grp==k)
return answer_for_this element_using_array_length_len
return -infinity
}
```

How do I make this approach better? I used a sorted segment tree to find number of elements that are greater than A[i] and in the range of i-len to i. Can it be made more memory efficient(since it was partially accepted and I got memory limit exceeded via this method) or is there a non dp solution to this? Or is a 3d dp state not required?Thanks in advance!

Problem source?

https://www.hackerearth.com/challenge/hiring/Pocket-Aces-software-hiring-challenge/ The 3rd question on this one. Unfortunately I am not able to access the questions now.

I think dp state should be dp[i][j] where this state stores the best answer if the last element of ith segment is at jth position.

Approach looks solid. you might need to precompute the number of inversions for each subarray to speed it up. In addition, you only need to store two variables for your state (I'm not sure why

`len`

matters).If we dont store len how are we going to know the answer for the ith element? For example, right now my function goes as: ll rdx=answer_for_this_group + max(f(idx+1,grp+1,1),f(idx+1,grp,len+1)). If I dont know the length, how will I compute answer_for_this_group?

He means following:

Let

dp[i][j] be max score which we can achieve by distributing firstielements intojgroupsThen recurrence is:

dp[i][j] =max(dp[t][j- 1] +f(t+ 1,i)) where:j- 1 ≤t<iandf(l,r) is number of inversions in segment [l,r]In order to optimize this solution you should previously compute

f[l][r] over alll≤r, overall with trivial implementation, you can achieveO(n^{3}) which seems to be enough, sincen≤ 500Oh I get it now. Thanks!