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
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.
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.
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
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.
Because we want to find, maximum sum subarray “including” the A[i-1]/ A[i+1].