Here is my java Solution
/* package codechef; // don’t place package name! */
import java.util.;
import java.lang.;
import java.io.*;
/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner s=new Scanner (System.in);
int t=s.nextInt();
while(t–>0) {
int n =s.nextInt();
long ans[]= new long[n];
for(int i=0;i<n;i++) {
ans[i]=s.nextLong();
}
long left_Minsum[]=left_Minsum(ans);
long left_Maxsum[]=left_Maxsum(ans);
long right_Minsum[]=right_Minsum(ans);
long right_Maxsum[]=right_Maxsum(ans);
long f_ans=ans[0]-ans[1];
for(int i=0;i<n-1;i++) {
long diff=Math.abs(left_Maxsum[i]-right_Minsum[i+1]);
if(f_ans<diff) {
f_ans=diff;
}
diff=Math.abs(right_Maxsum[i+1]-left_Minsum[i]);
if(f_ans<diff) {
f_ans=diff;
}
}
System.out.println(f_ans);
}
}
static long[] left_Maxsum(long[] ans) {
long arr[]= new long [ans.length];
long max=ans[0];
long max_far=ans[0];
arr[0]=ans[0];
for(int i=1;i<ans.length;i++) {
max_far=Math.max(ans[i], max_far+ans[i]);
max=Math.max(max_far, max);
arr[i]=max;
}
return arr;
}
static long[] right_Maxsum(long[] ans) {
long arr[]= new long [ans.length];
int n=ans.length;
long max=ans[n-1];
long max_far=ans[n-1];
arr[n-1]=ans[n-1];
for(int i=n-2;i>=0;i--) {
max_far=Math.max(ans[i], max_far+ans[i]);
max=Math.max(max_far, max);
arr[i]=max;
}
return arr;
}
static long[] right_Minsum(long[] ans) {
long arr[]= new long [ans.length];
int n=ans.length;
long max=ans[n-1];
long max_far=ans[n-1];
arr[n-1]=ans[n-1];
for(int i=n-2;i>=0;i--) {
max_far=Math.min(ans[i], max_far+ans[i]);
max=Math.min(max_far, max);
arr[i]=max;
}
return arr;
}
static long[] left_Minsum(long[] ans) {
long arr[]= new long [ans.length];
long max=ans[0];
long max_far=ans[0];
arr[0]=ans[0];
for(int i=1;i<ans.length;i++) {
max_far=Math.min(ans[i], max_far+ans[i]);
max=Math.min(max_far, max);
arr[i]=max;
}
return arr;
}
}Preformatted text
public static void main(String[] args) throws IOException {
FastScanner sc = new FastScanner();
int t = sc.nextInt();
first: while (t-- != 0) {
int n = sc.nextInt();
long arr[] = sc.readArrayLong(n);
long leftdp[][] = new long[n+1][2];
long rightdp[][] = new long[n+1][2];
// Initializing the max and min from left to the first element from the left
leftdp[0][0] = arr[0];
leftdp[0][1] = arr[0];
for(int i = 1; i < n; i++)
{
//updating the max and min from left upto i using dp
leftdp[i][0] = max(leftdp[i-1][0],0) + arr[i];
leftdp[i][1] = min(leftdp[i-1][1],0) + arr[i];
}
// Initializing the max and min from right to the first element from the left
rightdp[n-1][0] = arr[n-1];
rightdp[n-1][1] = arr[n-1];
for(int i = n-2; i >= 0; i--)
{
//updating the max and min from right upto i using dp
rightdp[i][0] = max(rightdp[i+1][0],0) + arr[i];
rightdp[i][1] = min(rightdp[i+1][1],0) + arr[i];
}
long ans = 0;
for(int i = 0; i < n-1; i++)
{
// absolute difference between minimum from left upto i and maximum from right upto i+1
ans = max(ans,Math.abs(leftdp[i][1] - rightdp[i+1][0]));
// absolute difference between maximum from left upto i and minimum from right upto i+1
ans = max(ans,Math.abs(leftdp[i][0] - rightdp[i+1][1]));
}
System.out.println(ans);
}
}
Java Solution
Can anyone explain this code in a simpler language? I am unable to understand it completely.
Why do we need to calculate LeftMin and LeftMax and RightMin and RightMax, i.e. why do we need to iterate from left to right as well as from right to left while performing DP over the iterations in both cases?
Please explain.
I can try to explain it again:
Imagine, we sit on an element. Now we see two groups of elements of the array:
-
Group towards the right of the element we sit on.
-
Group towards the left of the element we sit on.
To calculate RightMax, we have a choice of including the current element with the group of elements on the right to maybe form a bigger “Delish value”.
Similarly,
We see the left group of elements. We have a choice of including the current element(the one we are sitting on) with the group of elements on the left to maybe form a larger “Delish Value”(in case of left max) OR smaller “Delish Value”(in case of left min).
Hope it helps 
1 Like
Thank you! I think i understand it now. 