Not able to find logic

#1

I am trying to solve this question from leetcode…
1043. Partition Array for Maximum Sum

Here can you help me to come up with the logic which can construct that array… whose sum is required.
Thanks

#2

hello @ashishnnnnn

Problem asks for to partition array in some parts (each partition of length at most K) such that replace each element in partition by max element in that partition then total sum should be maximised.

For K = 1, trivial solution to consider each element as one partition then max sum = Sum of all elements
For K = 2, check for previous k - 1 elements i.e. previous 1 element.
Then decide between whether or not increase size of partition
e.g. For each two elements, Max of (2 * max element, sum of each element with k - 1)
For K = 3, check for previous k - 1 elements i.e. previous 2 elements.
e.g. For each three elements, Max of (3 * max element, earlier result of partition of size 2 of first two or last two elements + remaining element)

From pattern we have overlapping subproblem of computation of parition of size of k - 1 and optimal substructure (finding max sum), this calls for dyanamic programming.

dp[i] record the maximum sum we can get considering A[0] ~ A[i]
To get dp[i] , we will try to change k last numbers separately to the maximum of them,
where k = 1 to k = K .

  int maxSumAfterPartitioning(vector<int>& A, int K) {
        int N = A.size();
        vector<int> dp(N);
        for (int i = 0; i < N; ++i) {
            int curMax = 0;
            for (int k = 1; k <= K && i - k + 1 >= 0; ++k) {
                curMax = max(curMax, A[i - k + 1]);
                dp[i] = max(dp[i], (i >= k ? dp[i - k] : 0) + curMax * k);
            }
        }
        return dp[N - 1];
    }
#3

hii… i am not able to understand this properly… can you explain this on the phone or something if possible. it like memorizing the code… please if possible expain me on phone.Hope you understand.
Thanks

#4

@ashishnnnnn
have u solved LIS problem?

this problem is slight variation of that.

if u have any issue then first try to come up with recursive solution(its easy just do what they are saying).

#5

No… i haven’t solved lis… not seen the video

#6

Can you write the recursive solution.

#7

i would suggest to finish the dp playist of ur course.
it has covered almost all the types of dp problem.

recursion

ans([i…n-1]) = max([i…j] + ans([ j+1 . …n-1]) // where j-i +1 <=k

this is recursive solution ( i have done nothing )
what they have explained in english ,i have written the same in expression form.

now only thing is use an array to memoise the result

#8

Do you are talking about lis… ??

#9

no , the original problem that u asked

#10

Is this problem somewhat related to lis??

#11

no not exaclty , i m talking about technique.

the technique that is being used here is very much similar to Lis technique.

so if u have done lis before, solving this probllem will be easy.