### gur_chella's blog

By gur_chella, history, 20 months ago, ,

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)