vatsalseth33's blog

By vatsalseth33, history, 4 years ago, In English

Problem : Given an array A of integers,you can remove some elements as per your wish without changing the order of the remaining elements. After removing, value of A becomes sum(i*A[i]) from i = 1 to K(new size of A). Find maximum value of A possible after modification.

Example:
A = [-1,-9,0,5,-7]

Answer = 14 (remove -9 and -7 so value = -1*1 + 0*2 + 5*3)
I feel it is dp but cannot visualise it. Can anyone please help me out here?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can write dp[i][j], i — which element you take in A array, j — how many elements did you already took, dp[i][j] — value, max sum, if you took j elements from first i in array A.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what are the constraints on size of the array

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it