Help needed in DP question

1

Remove array end element to maximize the sum of product.
question link: Remove array end element to maximize the sum of product - GeeksforGeeks
I am not able to do it with Tabulation method.
Can anyone help me in writing the code via tabulation method.

Thanks for advance.

2

dp[i][j] stores the answer for the range [i, j]. So we can either pick A[i] next and add the answer for range [i+1, j] or we can pick A[j] and add the answer for range [i, j-1]. And also, the final answer will be dp[0][n-1]. So, for doing it bottom up, we can have the following base cases : dp[i][i] = A[i] * n. For all 0<=i<n. Then, dp[i][j] = max(A[i] * (n-j-i) + dp[i-1][j], A[j] * (n-j-i) + dp[i][j-1]).

3

Thanks …
But I have a doubt. Hope you will clear it.

  1. In base case .dp[i][j]=A[i]n. Actually in this case you are looking in subarray (i…i) (starts at i and ends also at i)
    So for this… Number of elements already removed are 0 because there is only one element in this subarray. Hence answer should be A[i]    (No. of elements already removed+1)==A[i]*(0+1).

  2. dp[i][j] = max(A[i] * (n-j-i) + dp[i-1][j], A[j] * (n-j-i) + dp[i][j-1]).
    What does (n-j-i) value represent. And how this value comes.

Please elaborate a little more.
Sorry for my bad English.
Thanks …

4

We are reversing the process here in this solution. The problem states that we remove elements from the two ends of the array. So when there is only one element left to be removed, then it is the nth element that you are removing in the process.
And for the second question, my bad, it is actually (n-j+i). The reason for this is simple. Consider the case, n=5 and we are looking for dp(1, 3). So as you can see we have already removed A[0] and A[4]. So, for the next number we remove, we multiply it by 3 (i.e. number of elements already removed + 1).

5

Thanks for helping me .
Keep Coding!!!