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!