Can anyone pls tell where i am going wrong in this solution…
sol_1
I used the same approach… and got ACed when i did this :
sol_2
Thank you in advance !! 
3 Likes
So, finally, after reading the editorials several times and after searching for some AC solutions, I finally got AC with my solution in C++:
/* Problem DELISH @Codechef JUN13 Long Contest
*
* Main idea is to use DP approach to solve problem in linear time.
* We need to maintain 4 vectors that will store:
* - Max value of delish starting from left
* - Max value of delish starting from right
* - Min value of delish starting from left
* - Min value of delish starting from right
*
* Now, since the value of a partial sum is always either >= 0 or <=0
* it is safe to assume that the optimal indexes i,j,k and l
* which form the intervals to substract are in fact contigous.
* This is because either we add a value to one of them and increase it
* , or we add it to the other one which also increases it, towards the
* first interval. This yields, wlog, the optimal answer. */
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long int LL;
#define put(x) printf("%lld\n",x)
vector<LL> max_sum_left(int N, vector<LL> arr)
{
vector<LL> res(N);
for(int i = 0; i < N; i++)
{
res[i] = 0;
}
res[0] = arr[0];
LL currMax = arr[0];
for(int i = 1; i < N; i++)
{
currMax = max(arr[i],arr[i]+currMax);
res[i] = max(res[i-1], currMax);
}
return res;
}
vector<LL> min_sum_left(int N, vector<LL> arr)
{
vector<LL> res(N);
for(int i = 0; i < N; i++)
{
res[i] = 0;
}
res[0] = arr[0];
LL currMin = arr[0];
for(int i = 1; i < N; i++)
{
currMin = min(arr[i],arr[i]+currMin);
res[i] = min(res[i-1], currMin);
}
return res;
}
vector<LL> max_sum_right(int N, vector<LL> arr)
{
vector<LL> res(N);
for(int i = 0; i < N; i++)
{
res[i] = 0;
}
res[N-1] = arr[N-1];
LL currMax = arr[N-1];
for(int i = N-2; i >= 0; i--)
{
currMax = max(arr[i],arr[i]+currMax);
res[i] = max(res[i+1], currMax);
}
return res;
}
vector<LL> min_sum_right(int N, vector<LL> arr)
{
vector<LL> res(N);
for(int i = 0; i < N; i++)
{
res[i] = 0;
}
res[N-1] = arr[N-1];
LL currMin = arr[N-1];
for(int i = N-2; i >= 0; i--)
{
currMin = min(arr[i],arr[i]+currMin);
res[i] = min(res[i+1], currMin);
}
return res;
}
LL compute(int N, vector<LL> arr)
{
LL maxDiffAbs = arr[0]-arr[1];
vector<LL> leftMax = max_sum_left(N,arr);
vector<LL> leftMin = min_sum_left(N,arr);
vector<LL> rightMax = max_sum_right(N,arr);
vector<LL> rightMin = min_sum_right(N,arr);
LL diff;
for(int i = 0; i < N-1; i++)
{
diff = leftMax[i]-rightMin[i+1];
if(diff >= maxDiffAbs)
maxDiffAbs = diff;
diff = rightMax[i+1]-leftMin[i];
if(diff >= maxDiffAbs)
maxDiffAbs = diff;
}
return maxDiffAbs;
}
int main()
{
int t,dim;
scanf("%d",&t);
for(int i = 0; i < t; i++)
{
scanf("%d",&dim);
vector<LL> arr;
for(int j = 0; j < dim; j++)
{
LL elem;
scanf("%lld",&elem);
arr.push_back(elem);
}
LL ans = compute(dim,arr);
put(ans);
}
return 0;
}
Thanks for this enlightening editorial @pragrame, which allowed me to write what I believe to be a clean solution for this problem!
Keep the good work up 
I hope I can also devote some of my time to understand the problem W-string a bit better and hopefully code a solution for it as soon as my time allows me to do so!
I hope I can really improve something with this good contest
Also, @xpertcoder, Thanks for your words! As you probably noticed, those problems are easy ones and those are the concepts which I can say that I feel most comfortable with, so, as you can see I still have a loong way to go 
Best regards,
Bruno
17 Likes
I made 2 functions using Kadane’s algorithm for max and min.
Function max gave me i,j,sum1.
Function min gave me k,l,sum2.
I took four cases.
1)max(0,arr.length-2) and min(j+1,arr.length-1) result1=Math.abs(sum1-sum2).
2)min(0,arr.length-2) and max(l+1,arr.length-1) result2=Math.abs(sum1-sum2).
3)max(1,arr.length-1) and min(0,i-1) result3=Math.abs(sum1-sum2).
4)min(1,arr.length-1) and max(0,k-1) result4=Math.abs(sum1-sum2).
I took maximum of all four results.I satisfied all given cases as well as cases in comments still I got WA always any help or case where it fails please 
:(…
@sid4art i did the same thing and got WA!
http://www.codechef.com/viewsolution/2276586
Can someone please point out what is wrong with this approach?
By same reasoning , one can implement Kadane algorithm too.
Can anyone explain me the output for
5
10 3 1 2 9
The output according to setter’s or tester’s code is 12. How?
@dsahapersonal assuming t=1,n=5,d={10,3,1,2,9}, that is the correct answer ! We need to basically find two contiguous subarrays (no intersecting point) such that the absolute difference(if the diff is negative,it turns positive) between the sum of each subarray is maximum .Now,the main thing to note here is that the length of the subarray could also be 1. Therefore , if you consider these two subarrays : {10,3} and {1} then the difference is absolute(1-(10+3))=absolute(-12) = 12 ! Also if you take any other pair of subarrays ,you will find that the absolute difference is not greater than that.
The sixth function is wrongly written. It should be leftmost not rightmost.
HardRightMax(i) = Maximum value of the sum of a contiguous subarray whose leftmost point = i.
The above solution provided in tutorial is giving tle while submitting in the java and the same solution give ac while submitting in java why?
Java Solution->https://www.codechef.com/viewsolution/21872923
C++ Solution->https://www.codechef.com/viewsolution/21872897
Not really. In your example, you say LeftMin(j) - RightMin(j+1) is larger. But note that LeftMin(j) <= LeftMax(j). So your case will be considered (and potentially bettered) in the check for LeftMax(j) - RightMin(j+1). You can check that the same will happen with comparing other pairs - wherever you compare difference of “max with max” or “min with min”.
2 Likes
really… that annoying… coding right… it’s better to understand someother code(esp. above tutorial) than that purely written code…
same story… here :-/
haha… I knew it bro… I was jst thinking, in what world karlheinz would be, when he wrote the code… I mean how a person can write such a code… I think he himself cant xplain that…
1 Like
think it this way… Compare your present knowledge with the knowledge you had when you started competitive coding… we all know that it must be way better than at that time… Now you are a part of a dedicated community whose members are not only working for themselves but are working for each other… At least you are better than your mates who dont even knw a bit about competitive programming… At least we try our best to solve these tuff problems and become part of a big competitions… Cheerup bro these conditions will reoccur… all what we need is unstoppable efforts… 
4 Likes
Well, @devanshug, you’re right and it is indeed a lot better now than it was before… I even got to write some Simple problems as a setter and I actually think I managed to write good tutorials here on forums… But sometimes I feel that this is all I got… Maybe it’s the lack of time that makes me think this way, but it’s still very frustrating and demotivating… I think I will try to work as hard as university allows me, in order to get a little bit better though Thanks for your words
1 Like
dafaq is this code !!!whre’s a main() ??
1 Like
@kuruma, Being relatively new to competitive programming and algorithms besides the constraints due to university, i feel the same as i have not been able to solve more than 3 problems but each time we get stuck we learn something new(be it the simplest of things) but that is what should drive us as these little things go a long way in enhancing our programming skills. Bit by Bit, Bytes of knowledge can be acquired, learnt and applied to improve our speed and efficiency in solving more problems. And considering that you are a lot better than before, its an achievement in itself. Chin up!
2 Likes
@spandanpathak, It has a main… but nothing else is understandable. Probably we first need to replace all those variable to simple ones and the format it to understand where the functions start and end… 