Given an array of length N with elements array[i] (negative integers inclusive), maximize the Score of the array.
Score of the array = -seg[1]+seg[2]-seg[3]+seg[4].... where all seg[i] are the sum of non-intersecting segments of the array which constitute all of the array when combined. We are also provided with an integer K, meaning the array must be divided exactly into K segments.
We aren't given constraints in the problem statement. What is the optimised approach for this question.
Could anyone share the solution with DP state[N][K]
I guess yes? the DP state is $$$dp[i][j]$$$ meaning that the optimal score of the array when considering index i and we already have j segments. Initially, $$$dp[0][0]=0$$$ and for every i and j we have:
dp[i][j]=dp[i-1][j-1]+(-1 if j%2 else 1)*a[i] (start a new segment for a[i])and:dp[i][j]=dp[i-1][j]+(-1 if j%2 else 1)*a[i] (append a[i] to previous segment)This will give a time complexity of $$$O(n^2)$$$ . Correct me if I'm wrong I'm also a newbie in CP...Please Exaggerate.
maybe posting pseudocode will be better.
its not dp simple greedy
I guess finding the minimal elements and assign them to the $$$k/2$$$ negative sign intervals will be achievable?
didn't get what you are trying to say but greedy is
assume if 1st element is negative then simply answer is sum of absolute value of all elements
otherwise we give seg1 to any prefix and it it benificial to end prefix in such a place such that seg2 starts with positive elements then we can just take absolute of all values from that index so just find maximum of sum(pref[i])+sum(suff[i+1]) for all i where suff[i] contain sum of absolute values of suffix from i to n and pref[i] is sum of from 1 to i
if you want to do it with dp you can use dp[i][0] and dp[i][1] where 0 represents negative and 1 represents positive then
dp[i][0]=-a[i]+max(dp[i-1][0],dp[i-1][1])
dp[i][1]=a[i]+max(dp[i-1][0],dp[i-1][1])
We have to divide the array mandatorily into K segments
i guess greedy works
Explain the approach. I assume you think we can change segment so as to add negative number positively into our sum and accordingly change the segment again to add positive numbers as it is into our sum, but we should take into consideration that there is a condition to divide array into K segments only.
oh sorry i missed we have to cut it in exactly k segments
Maybe the state of dp[i][j][k] works? i meaning ending at index i, j meaning last idx of start of current segment and k meaning remaining segments.
O(N*N*K) is way too slow. Could we have something in O(N*K)?
first comment solution in n*k
I tried it with a 3d dp way with states as current index , number of segments left and a flag variable of wheather segment is ending here or not. it is much like a knapsack dp problem with some variation
my recursive dp solution — https://p.ip.fi/33m8
Using flag is not preferrable since it gives WA. The index where the segment started is more preferrable instead.
I don't think so do itself. Takes care of the best possible combination when I reach some state and states are dynamic in both cases If you have any counter test case please refer it
very simple dp, let dp[i][k] be maximum score made up to index i with k segments, now if k is pair means you will take max of dp[j][k-1]-pref[j-1],1<=j<i(use 1 indexed for prefsum) else take maximum dp[j][k-1]+pref[j-1], then score if k is pair you add pref[i] to that max chosen else you minus pref[i], now to in order not to loop over all j's u can use map such that map1[k] is max dp[j][k-1]-pref[j-1] and map2[k] is max dp[j][k-1]+pref[j-1],i hope u understand my explanation.