MMSUM - Editorial

Setter and tester solutions are for the problem Kitchen Timetable (KTTABLE)

I tried the same but the solution given is not working…Is it for the same problem…i doubt…???

Can this problem be solved using divide and conquer?
Tried,but then got WA.

Please Help me with this !
this is the algorithm applied

1)eliminate one element at a time in the array
2) correspondingly find the maximal sub array sum (by the standard algorithm)
3) store it in another array
4)sort this array and print the last(largest) element.

LINK OF MY SOLUTION:-CodeChef: Practical coding for everyone

This algorithm doesn’t work on n=2

1 Like

according to your algorithm
for Test case
n=5
input
1 -2 3 -2 5
output will be 12

This can be done in just 1 loop with O(1) space cost by adapting Kadane’s method, rather than requiring 3 loops and O(n) (additional) space cost as in the solution shown by setter/tester.

Example https://www.codechef.com/viewsolution/10259181
which is a simplified version of https://www.codechef.com/viewsolution/10214880

We have to modify this logic
for i=2…N-1:
answer = max(answer, E[i-1] + S[i+1])

As
for(i=1;i<=N;i++{
if(i-1<1){
answer = max(S[i+1],answer);
}else{
if(i+1==N+1){
answer=max(answer,E[i-1]);
}else{
answer=max(answer,E[i-1]+S[i+1];
}

}
then it will work for N=2 as well.

}

@godmar, I too applied the same algorithm and ended up doing it in a single pass.
Link to the solution

It doesn’t seem to give the correct answer.

https://www.codechef.com/viewsolution/10260527
where am i going wrong?

Alternate solution:
Got AC
Slightly different from editorial.
Keep two arrays dpWithDelete and dpWithoutDelete which keep track of the MaxSum with and without delete.
Link
https://www.codechef.com/viewsolution/10193855

Please approve.

2 Likes

calculate two array forward and backward which store the current maximum sum till that index .and now for any index calculate backward[i+1]+forward[i-1] for that index .which indicates the maximum sum for that index if that particular index value is not used… and you have to store maximum value in a variable (which indicate if no element of array is remove)…

link to solution:CodeChef: Practical coding for everyone

@vijju123 @admin

DIFFICULTY: Easy, But this question has tag Medium. Plz. look into this.

answer = -INFINITY
current = 0
for j=1..N:
    current = max(A[j], current + A[j])
    answer = max(answer, current)
    E[j] = current

Here E[j] = current is given, I am having doubt why it’s not E[j] = answer as till i answer is the maximum subarray sum

How to solve this if at most K removals are allowed?

There’s a O(nk) algorithm, but I don’t know of any O(n) algorithms for this.
let dp[i][j] denote the maximum sum ending at i with j removals

ll solve(){
    int n,k;
    cin>>n>>k;
    ll seq[n];
    ll dp[n+1][k+1];
    ll ans=-1e18;
    for(int i=0;i<n;i++){
        cin>>seq[i];
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        dp[i][0]=max(seq[i-1],seq[i-1]+dp[i-1][0]);
      //Either this or the previous with 0 removals 
        ans=max(ans,dp[i][0]);
        for(int j=1;j<=k;j++){
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]+seq[i-1]);
//Either this and previous with j removals or
//Remove this and previous with j-1 removals
            ans=max(ans,dp[i][j]);
        }
    }
    return ans;
}

Sadly It’s not a question so I can’t verify my code.

1 Like

That’s awesome !!. it’s correct. INOI 2011 had the question, Took me two hours to solve.

Because we want to find, maximum sum subarray “including” the A[i-1]/ A[i+1].

Nice solution with dp! :+1:
I tried to shorten your code: ideone