• 33

Country: United States

Comment hidden because of low score. Click to expand.
37
of 39 vote

An O(n) solution is possible.

We consider all "split points", i.e. points such that one subarray lies to the left of it, and one to the right, and compute the best for each possible split point.

Dynamic programming works.

Given Array A[1,...n]

Using the standard dynamic programming algorithm, we can compute for a given i, the maximum and minimum sum subarrays in A[1...i] and A[i+1 ... n]. Note that the point between i and i+1 is a split point.

This can be done by making two passes once from 1 to n, and other from n to 1 and give us four arrays with the max and min sub-array sums.

Now given the above four arrays, for split point between i and i+1, we can take the max and min combinations (max from right, min from left and max from left, min from left), and get the combination which gives the better result.

Once we have the max for each split point, we get the global optimum.

O(n) time, O(n) space.

Comment hidden because of low score. Click to expand.
0

Nice solution Loler. I think it will work

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

@loler: so let's run it on [4, -1, 7]
For i:1 so we divide array as  & [1,2]
[max 4 min 4] [max 7 min 6]
For i:2 so we divide array as [0,1] & 
[max 4 min 3] [max 7 min 7]
so let's compare all the min and max arrays for each i i.e. split point.
So we get 3 as the answer(7-3)
Is this what you mean?

Comment hidden because of low score. Click to expand.
2

Looks like you got tricked into answering a live competition question: codechef.com/JUNE13/problems/DELISH

Comment hidden because of low score. Click to expand.
9

@Loler: the solution which you presented is still O(n^2). Because for each split point you are finding max & min sub arrays in either sides in O(i) and O(n-i), for split at i. So, for all split points, the order comes out to O(n^2).

Comment hidden because of low score. Click to expand.
2

@frager +1. I agree this is a quadratic algorithm. @Loler, can you post the code?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@frager: but you can do it (computing the max/min) subarrays for each split point in O(n) if you cache previous results (hence O(n) space complexity). When you are at A[i] the max subarray is either max A[i-1] extended with A[i] or if this extension goes below 0 then the max subarray is the same subarray as for A[i-1].

Tell me if I'm wrong.

Comment hidden because of low score. Click to expand.
2

@oOZz: I came up with the same algorithm as @Loler. Below is the code (ugly but I did it during my lunch break). It is O(n) time and O(n) space and passes the dreaded {4,-1,7} ;) But didn't test it extensively. P.S. I am full of respect for people who can come up and code it within 45mins, without a compiler and during an interview (stress). Took me 1hours with a compiler.

``````public static int computeMaxDiff(int[] A) {
int[] max = new int[A.length];
int[] min = new int[A.length];
max = A;
min = A;
int len = A.length-1;
int currentMax = max;
int currentMin = -min;
for(int i = 1; i <= len; i++) {
currentMax += A[i];
if(currentMax > 0) {
max[i] = Math.max(currentMax, max[i-1]);
} else {
max[i] = max[i-1];
currentMax = 0;
}

currentMin += -A[i];
if(currentMin > 0) {
min[i] = -Math.max(currentMin, -min[i-1]);
} else {
min[i] = A[i];
if(A[i] < 0) {
currentMin = -A[i];
} else {
currentMin = 0;
}
}
}

int[] revMax = new int[A.length];
int[] revMin = new int[A.length];
revMax = A[len];
min = A[len];

currentMax = revMax;
currentMin = -revMin;
for(int i = len-1; i >= 0; i--) {
currentMax += A[i];
if(currentMax > 0) {
revMax[len-i] = Math.max(currentMax, revMax[len-i-1]);
} else {
revMax[len-1] = revMax[len-i-1];
currentMax = 0;
}

currentMin += -A[i];
if(currentMin > 0) {
revMin[len-i] = -Math.max(currentMin, -revMin[len-i-1]);
} else {
revMin[len-i] = A[i];
if(A[i] < 0) {
currentMin = -A[i];
} else {
currentMin = 0;
}
}
}

int maxDiff = Integer.MIN_VALUE;
for(int i = 0; i < len; i++) {
int currMax = Math.max(Math.abs(max[i] - revMin[i]), Math.abs(min[i]-revMax[i]));
if(currMax > maxDiff) {
maxDiff = currMax;
}
}
return maxDiff;
}``````

If we want more - like exactly the subarrays we need to store the start/end indices for each split too (doesn't change the time complexity order, only the constant)

Comment hidden because of low score. Click to expand.
0

@Up: two things:
1) noticed I copied my solution with a bug, while calculating the "revMax/Min" there should be revMin = A[len]; instead of min = A[len];
2) depending on how we interpret the question there might be needed a slight change in the code. For instance what should be the output for [-1,-2,-3]. Should it be 4 (as abs( (-3-2) - (-1) )) or should we take the whole array and treat an empty array as the second one which would give us abs( (-3-2-1) - 0) = 6?

Comment hidden because of low score. Click to expand.
0

@Anonymous. Respect my friend! The code mostly works (see below), but it's still impressive to come up with a DP solution in 1 hour during lunch. (+1) I also agree with you that the DP problems are hard to solve in 45 mins without a compiler and therefore, they're better suited for coding competitions than job interviews.

Your code for input [-1,-2,-3] fails. It outputs 1, but neither 4 nor 6. I've asked the same question to @LAP for clarification whether the empty set is a valid subarray and its sum is 0, but he/she didn't answer. I'd assume that it is. Then IMO, [-1,-2,-3] should return (0 - (-1,-2,-3)) = 6 and [4,-1,7] should return ((4,-1,7) - 0) = 10.

I've also just made a small change to the code that I posted above. It works with the empty set assumption. Though it's a O(N) time and O(1) space and only 20 lines, no one seems to not like it LOL Happy coding!

Comment hidden because of low score. Click to expand.
0

@oOZz: the [-1,-2,-3] result is incorrect because I pasted my code with a bug to this site (long story short I couldn't do a ctrlc/ctrlv :). I mentioned it above.

Also I agree with that DP problems suck for interviews. Hopefully I will not have one (or at least a hard one) during my G interview today :))

Comment hidden because of low score. Click to expand.
0

@aka: Yes something like that.

@eugene: Oops. Well played by LAP I suppose :-), and looks like it might be too late to delete now.

@frager/oOZz: It is O(n). Just store the intermediate results of Kadane's algorithm... (Kadane's is what I mean by "standard dynamic programming algorithm".)

@oOZz: During an interview they don't expect perfect code which will compile at the get go. If you want to use some library method, you can just assume it. I would say it is easier to write code in an interview, than using a compiler: you won't get bogged down by the useless details (like does strcpy take dst first or src?) and can concentrate on the parts that matter.

@Anonymous: I don't see a problem asking DP questions. The point of the questions is not to see whether you get the answer or not, but to see how you tackle it. You will be judged relative to other candidates on the same question (at least in Google), so everyone is in the same boat.

Sorry if I missed responding to someone.

Comment hidden because of low score. Click to expand.
0

@Loler: Do you work for Google? Wonderful!

Comment hidden because of low score. Click to expand.
0

@Dumbo. The information about the judging relative to other candidates is public. Gayle has herself said it multiple times. Even the recruiters tell you that, I believe.

Comment hidden because of low score. Click to expand.
0

@Loler: Wonderful Loler, nice to know that great talent is around. Wanted to ask you for a favor - I have been working on question?id=12708671. Thought hard on the problem for days together and came up with a solution. Could you kindly verify if my idea works? [Kindly excuse my trumpeting there]. Apologies to all who find my post irrelevant to the current context - btw any other way of 1-1 communication possible here?

Comment hidden because of low score. Click to expand.
0

There is some issue with this DP approach, because the max/min sum of A[1..i] can not be generated from A[1..i-1].
Here are two examples:
{-6 5 -7 6} => Min: {-6 5 -7 } = -8, Min = {6} = 6, Diff= 14
{-6 5 -7 2} => Min: {-7}, Max = {5}; Diff = 12
The Min for {-6 5} is {-6}, but from this Min, we cannot get Min for {-6 5 -7} = -8
Also @oOZz's code always assumes the min/max running sum continuing decrease/increase. They may decrease, increase and then decrease.

The split point approach is still valid.

Comment hidden because of low score. Click to expand.
0

@Dumbo: Try freenode IRC channel #algorithms if you have any doubts in algorithms.

Comment hidden because of low score. Click to expand.
0

For the reverse max/min, we don't even need to store the result in array. We can simply make a reverse pass and at every point, we have the max and min. Using these two variables, we can simply calculate the absolute difference. The largest different would be the answer.

Comment hidden because of low score. Click to expand.
0

@Anonymous. There are lots of bug in your code, apart from the one you already know.
1) Take input [-4,5], in this case your code will find max as -4+5=1 which is wrong, max should be 5, same for the min case.
2)I think your logic for calculating the min array is also wrong, recheck it one.
Apart from these bugs, nice solution :) . Do post about your G interview :)

Comment hidden because of low score. Click to expand.
0

@sniper: about [-4,5] I think it should be |5-(-4)| = 9 and that's how my code acts :) But you are right I wasn't 100% sure how to interpret the question for instance what should be the result for [1,5]. Should it be |(5+1)-0| = 6 or |5-1|=4? It all depends is an empty subarray an array. I assumed no.

About the min array I still didn't find a counterexample that would give me an incorrect solution but indeed there might be bugs :)

The G interview was good, will post the question soon but it was very easy :)

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

@oOZz's solution does work for an array containing only positive numbers. For example, [8, 1, 1, 1].

Comment hidden because of low score. Click to expand.
1
of 1 vote

I come up with the same algorithm as @Loler. I implement it in Python. Here is the code:

``````def max_contiguous_subarray_abs_diff(A):
n = len(A)
assert n > 0
left_min, left_max = left_min_max(A)
right_min, right_max = left_min_max(A[::-1])
max_diff = 0
for i in xrange(n - 1):
smallest = min(left_min[i], right_min[n - 2 - i])
largest = max(left_max[i], right_max[n - 2 - i])
diff = abs(largest - smallest)
if max_diff < diff:
max_diff = diff
return max_diff

def left_min_max(A):
n = len(A)
pre_min =  * (n + 1)
pre_max =  * (n + 1)
pre =  * (n + 1) # :i
for i in xrange(0, n):
pre[i + 1] = pre[i] + A[i]
pre_min[i + 1] = pre_min[i]
if pre_min[i + 1] > pre[i + 1]:
pre_min[i + 1] = pre[i + 1]
pre_max[i + 1] = pre_max[i]
if pre_max[i + 1] < pre[i + 1]:
pre_max[i + 1] = pre[i + 1]
left_min = [None] * (n - 1)
left_max = [None] * (n - 1)
for i in xrange(0, n - 1):
left_min[i] = pre[i + 1] - pre_max[i]
left_max[i] = pre[i + 1] - pre_min[i]
return (left_min, left_max)

A = [2, -1, -2, 1, -4, 2, 8]
print(A, max_contiguous_subarray_abs_diff(A))
A = [8, 1, 1, 1]
print(A, max_contiguous_subarray_abs_diff(A))
A = [4, -1, 7]
print(A, max_contiguous_subarray_abs_diff(A))``````

Comment hidden because of low score. Click to expand.
0

``````*********** Max Difference disjoint consecutive sets *************

# A: the input array.
# decider: a function that choose whether we are find the min or max sum subarray of A[0:i]
# retv: T: min or max sum
def fill_array(A, decider):
cur = 0
T = []
for a in A:
cur += a
if decider(cur):
cur = 0
T.append(cur)
return T

# A: input array
# return: the maximum diff
def max_diff_disjoint(A):

def find_min(a):
return a > 0
def find_max(a):
return a < 0

left_min = fill_array(A, find_min)
left_max = fill_array(A, find_max)
right_min = fill_array(reversed(A), find_min)
right_max = fill_array(reversed(A), find_max)

max_diff = -float(‘inf’)

for i in range(len(A)):
diff = right_max[i] - left_min[i]
max_diff = max(diff, max_diff)

diff = left_max[i] - right_min[i]
max_diff = max(diff, max_diff)

return max_diff``````

Comment hidden because of low score. Click to expand.
0

I agree this is the best answer on the board, but I think it is still wrong.

Consider: -10 7 -3 2 2 -20 1

The best split point considering everything left and right is between -20 and 1, where the best solution is -20 and 7.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Why does this answer have so many likes? It doesn't take into account that the first array can start not from the beginning but rather from any other positions and the same is true for the second array. Actually there are three split points in this task.
So, if we have an array {2, -4, -5, 3, 6, -1}, our split point will be:
Split point 1 goes after 2
Split point 2 goes after -5
Split point 3 goes after 6
And the solution will be {-4, -5} and {3, 6}

Comment hidden because of low score. Click to expand.
0

@debugxyahoo +1

Comment hidden because of low score. Click to expand.
0

Came up with the same algorithm, here's the code in Python:

``````DECREASING = 0
INCREASING = 1

def prepare(A, function, direction):
Z =  * len(A)
Y = [None] * len(A)
indices = range(len(A))
if DECREASING == direction:
indices.reverse()
first = 2
second = 1
seed = len(A) - 1
delta = 1
elif INCREASING == direction:
first = 1
second = 2
seed = 0
delta = -1
for i in indices:
if i == indices:
Z[i] = A[i]
Y[i] = (A[i], seed, seed)
else:
previous = i + delta
Z[i] = function(A[i], Z[previous] + A[i])
if Z[i] == A[i]:
start = i
else:
start = Y[previous][first]
result = function(Y[previous], Z[i])
if result == Z[i]:
stop = i
else:
stop = Y[previous][second]
Y[i] = [result, 0, 0]
Y[i][first] = start
Y[i][second] = stop
return Y

def check(U, V):
for i in range(len(U) - 1):
diff = abs(U[i + 1] - V[i])
if i == 0:
maximum = diff
index = 0
elif diff > maximum:
maximum = diff
index = i
return (maximum, index)

def find(A):
C = prepare(A, min, INCREASING)
B = prepare(A, max, DECREASING)
(maximum1, index1) = check(B, C)
D = prepare(A, max, INCREASING)
E = prepare(A, min, DECREASING)
(maximum2, index2) = check(E, D)
if maximum1 < maximum2:
print('From %d to %d' % (D[index2], D[index2]))
print('From %d to %d' % (E[index2 + 1], E[index2 + 1]))
else:
print('From %d to %d' % (C[index1], C[index1]))
print('From %d to %d' % (B[index1 + 1], B[index1 + 1]))

A = [2, -1, -2, 1, -4, 2, 8]
find(A)
A = [2, 2, 2, 2, -1, -1, -1, -1]
find(A)``````

Comment hidden because of low score. Click to expand.
0

Its important to consider that the smaller subarray might be both on the left and on the right hand from the split point. Here's a code:

``````def max_subarray(el,max_sf,max_eh,func):
if max_eh is None:
max_eh = el
max_sf.append(el)
else:
max_eh = func(el, max_eh + el)
max_sf.append(func(max_sf[-1], max_eh))
return max_eh

def maxsum(l):
min_sf,max_sf = [], []
min_eh,max_eh = None, None
for i in range(len(l)-1):
min_eh = max_subarray(l[i],min_sf,min_eh,min)
max_eh = max_subarray(l[-i-1],max_sf,max_eh,max)
max_sf = max_sf[::-1]
maxdiff = max_sf[-1] - min_sf
for i in range(len(l)-1):
if max_sf[i] - min_sf[i] > maxdiff:
maxdiff = max_sf[i] - min_sf[i]
return maxdiff

def metamaxsum(l):
return max(maxsum(l),maxsum(l[::-1]))

print metamaxsum([1,1,1,-1,-5,100])
print metamaxsum([2,-1,-2,1,-4,2,8])
print metamaxsum([-10,7,-3,2,2,-20,1])``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

the hell is everyone smoking... is everyone reading a different problem or am i? why do all these solutions including this up voted one not even answering the question at all? the sub arrays can start from ANYWHERE in the array, you're not looking for a "split point" to split the array into two... you're looking for two disjoint subarrays. Not sure if everyone is retarded or just me...

Comment hidden because of low score. Click to expand.
0

@Loler is the best algo i could think of. Re-writing in a simple to understand but longer code

``````public class DisjointContinguosSubArray {

public static void getTwoDisjointArrays(int[] arr){

List<List<Integer>> maxDiffList = new ArrayList<List<Integer>>();
int maxDiffSoFar = Integer.MIN_VALUE;

// O(N*N)
for(int i=0;i<=arr.length-2;i++){ // till -2, so we have one element the rightmost array // O(N)

//Combo1
List<Integer> leftMin = getMinSubsetArray(arr,0,i); // O(N) // get Min sub-array to the left of i(including) i.e 0 to i
List<Integer> rightMax = getMaxSubsetArray(arr,i+1,arr.length-1); // O(N) // get Max sub-array to the right of i(excluding)

//Combo2
List<Integer> leftMax = getMaxSubsetArray(arr,0,i); // O(N) //get Max sub-array to the left of i(including)
List<Integer> rightMin = getMinSubsetArray(arr,i+1,arr.length-1); // O(N)  // get Min sub-array to the right of i(excluding)

int diff1 = Math.abs(rightMax.get(0) - leftMin.get(0)); // Combo1's diff

int diff2 = Math.abs(leftMax.get(0) - rightMin.get(0)); // Combo2's diff

if(diff1>diff2){ // diff1 is bigger
if(diff1 > maxDiffSoFar){
maxDiffSoFar=diff1; // update maxSoFar
maxDiffList.clear();
}
}else{
if(diff2 > maxDiffSoFar){ // diff2 is bigger
maxDiffSoFar=diff2;  // update maxSoFar
maxDiffList.clear();
}
}
}

System.out.println("Two disjoint arrays : " + maxDiffList.get(0).toString() + " " +  maxDiffList.get(1).toString());
System.out.println("Max Diff : " + ( maxDiffList.get(1).get(0) - maxDiffList.get(0).get(0) ));

}

//get Min sub-array between points // O(N)
public static List<Integer> getMinSubsetArray(int[] arr , int i , int j){

int iMin = -1;
int jMin = -1;
int minSum = Integer.MAX_VALUE;
int iCurrent=  -1;
int jCurrent = -1;
int currentSum=0;

for(int k=i;k<=j;k++){
currentSum = Math.min(currentSum+arr[k], arr[k]);
if(currentSum == arr[k]){
iCurrent = k;
jCurrent = k;
}else{
jCurrent = k;
}

minSum = Math.min(minSum,currentSum);
if(minSum == currentSum){
iMin = iCurrent;
jMin = jCurrent;
}
}

// This List which is the result stored 0thIndex(min sum) 1thPosition(fromIndex of min sub-array) 2ndPosition(toIndex of min sub-array)
List<Integer> list = new ArrayList<Integer>();

return list;
}

//get Max sub-array between points  // O(N)
public static List<Integer> getMaxSubsetArray(int[] arr , int i , int j){

int iMax = -1;
int jMax= -1;
int maxSum = Integer.MIN_VALUE;

int iCurrent = -1;
int jCurrent = -1;
int currentSum = 0;

for(int k=i;k<=j;k++){
currentSum = Math.max(currentSum+arr[k], arr[k]);
if(currentSum==arr[k]){
iCurrent = k;
jCurrent = k;
}else{
jCurrent = k;
}

maxSum = Math.max(maxSum, currentSum);
if(maxSum == currentSum){
iMax = iCurrent;
jMax = jCurrent;
}
}

// This List which is the result stored 0thIndex(max sum) 1thPosition(fromIndex of max sub-array) 2ndPosition(toIndex of max sub-array)
List<Integer> list = new ArrayList<Integer>();

return list;
}

public static void main(String[] args) {
int[] arr = {2,-1,-2,1,-4,2,8}; // Works as expected
//int[] arr = {-1,-2,-3}; // Works as expected
getTwoDisjointArrays(arr);
}
}``````

Comment hidden because of low score. Click to expand.
3
of 3 vote

Use dp with kadane's algorithm for solving above problem...:-)

import java.io.*;
public class Main {

public static void main(String args[]) throws IOException
{
long a[]=new long;
long b[]=new long;
long max1[]=new long;
long min1[]=new long;
long max2[]=new long;
long min2[]=new long;
int i=0;
for(String s:arr)
{
a[i]=Integer.parseInt(arr[i]);
b[i]=-a[i];
i++;
}

long maxsofar=a,maxendinghere=a;max1=a;
for(i=1;i<n;i++)
{
//maxendinghere=maxendinghere+a[i]>0?maxendinghere+a[i]:0;
maxendinghere=maxendinghere+a[i];
maxendinghere=maxendinghere>a[i]?maxendinghere:a[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
max1[i]=maxsofar;
}
max2[n-1]=maxendinghere=maxsofar=a[n-1];
for(i=n-2;i>=0;i--)
{
//maxendinghere=maxendinghere+a[i]>0?maxendinghere+a[i]:0;
maxendinghere=maxendinghere+a[i];
maxendinghere=maxendinghere>a[i]?maxendinghere:a[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
max2[i]=maxsofar;

}
maxendinghere=maxsofar=b;
min1=-b;
for(i=1;i<n;i++)
{
//maxendinghere=maxendinghere+b[i]>0?maxendinghere+b[i]:0;
maxendinghere=maxendinghere+b[i];
maxendinghere=maxendinghere>b[i]?maxendinghere:b[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
min1[i]=-maxsofar;
}
maxendinghere=maxsofar=b[n-1];
min2[n-1]=-b[n-1];
for(i=n-2;i>=0;i--)
{
//maxendinghere=maxendinghere+b[i]>0?maxendinghere+b[i]:0;
maxendinghere=maxendinghere+b[i];
maxendinghere=maxendinghere>b[i]?maxendinghere:b[i];
maxsofar=maxsofar>maxendinghere?maxsofar:maxendinghere;
min2[i]=-maxsofar;
}
long globalmax=0;
/*
for(i=0;i<n;i++)
{
System.out.println(a[i]+" "+b[i]+" "+min1[i]+" "+max1[i]+" "+min2[i]+" "+max2[i]);
}
*/
for(i=1;i<n;i++)
{
long m1=max1[i-1]-min2[i];
m1=Math.abs(m1);
long m2=max2[i]-min1[i-1];
m2=Math.abs(m2);
m1=m1>m2?m1:m2;
globalmax=globalmax>m1?globalmax:m1;
}
System.out.println(globalmax);
}

}

Comment hidden because of low score. Click to expand.
1
of 1 vote

So abstract the list of ints to a list of three subsets.

list of numbers= {a, b, c} where a,b,c are sums of contiguous numbers in the array and a,b,c are contiguous.

Each of those subsets represents the sum of contiguous numbers in the array. We are looking for the highest and lowest. Note that it is impossible for A or C to have the same signage (positive or negative) as B. Also, if either A or C is the empty set, then the positive subset is the highest and the negative subset is the lowest. If both A and C are the empty set, then B is either the high subset or low subset based off of B's signage. Also lets specify that, B can never be an empty set unless both A and C are empty sets. Now the important thing to note here is that we are going to try to maximize the absolute value of B. This is important because it will allow us to take the highest absoulute value of either A or C and get the highest combined difference.

So let's take a look at some real numbers
n = {a, b, c}

``int[] array = {100, -500, 2, -7, 50, -51, 3, -2, 4, 300, -150 };``

so n = {100, -506, 305}

So here we can see we should grab the array that adds up to -506 (-500, 2, -7, 50, -51) and the array that adds up to 305 (3, -2, 4, 300).

So basically the algorithm is this
1) Pass through the array and calculate the sums
2) Figure out the largest absolute value the sub array B can be
3) Figure out if either A or C should be the other array

Here is some code that I wrote that does what I outlined above. It was written before I really understood why the codeworks so it could be prettied up, but I am too lazy to do so :)

``````// 2 -2 1 -1 3 12
int[] array = {100, -500, 2, -7, 50, -51, 3, -2, 4, 300, -150 };
int[] sumIndex = new int[array.Length];
int sum = 0;
int highEndIndex = 0;
int lowEndIndex =0;
int high = 0;
int low = 0;

for (int i = 0; i < array.Length; i++)
{
sum += array[i];
sumIndex[i] = sum;
if (sum > high)
{
high = sum;
highEndIndex = i;
}
else if (sum < low)
{
low = sum;
lowEndIndex = i;
}
}

bool isLowFirst = Math.Abs(low) > highEndIndex;
int startIndex = isLowFirst ? lowEndIndex : highEndIndex;
int offset = isLowFirst ? low : high;

for (int i = startIndex + 1; i < sumIndex.Length; i++)
{
if (i >= sumIndex.Length)
break;
sumIndex[i] -= offset;
if (!isLowFirst &&sumIndex[i] < low)
{
low = sumIndex[i];
lowEndIndex = i;
}
else if (isLowFirst && sumIndex[i] > high)
{
high = sumIndex[i];
highEndIndex = i;
}
}

int highestInLow = low;
int lowStartIndex = lowEndIndex;
for (int i = lowEndIndex; i >= 0 || i >= highEndIndex; i--)
{
int sumToCompare = i == 0 ? 0 : sumIndex[i-1];
if (sumToCompare> highestInLow)
{
highestInLow = sumToCompare;
lowStartIndex = i;
}
}

int lowestInHigh = high;
int highStartIndex = highEndIndex;
for (int i = highStartIndex; i >= 0 || i >= lowEndIndex; i--)
{
int sumToCompare = i == 0 ? 0 : sumIndex[i - 1];
if (sumToCompare < lowestInHigh)
{
lowestInHigh = sumToCompare;
highStartIndex = i;
}
}``````

Comment hidden because of low score. Click to expand.
0

NOTE: the second array is a SUBSET of either A or C if B is I-j, you should start with I-1 as the end of one of the potential arrays and j+1 as the start of one of the potential arrays.

Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution in C++ (based on the same idea as some other answers with O(n) running time) :

``````#include <algorithm>
#include <iostream>
#include <vector>

int computeMaxDiff(std::vector<int> L) {
int maxLeftNeg[L.size()], maxRightNeg[L.size()], maxLeftPos[L.size()], maxRightPos[L.size()];
int maxDiff = 0, j;
int tmp;

maxLeftNeg = L < 0 ? L : 0;
maxLeftPos = L > 0 ? L : 0;
maxRightNeg[L.size() - 1] = L[L.size() - 1] < 0 ? L[L.size() - 1] : 0;
maxRightPos[L.size() - 1] = L[L.size() - 1] > 0 ? L[L.size() - 1] : 0;
for (int i = 1; i < L.size(); ++i) {
maxLeftNeg[i] = (maxLeftNeg[i - 1] + L[i] < 0) ? maxLeftNeg[i - 1] + L[i] : 0;
maxLeftPos[i] = (maxLeftPos[i - 1] + L[i] > 0) ? maxLeftPos[i - 1] + L[i] : 0;
j = L.size() - 1 - i;
maxRightNeg[j] = (maxRightNeg[j + 1] + L[j] < 0) ? maxRightNeg[j + 1] + L[j] : 0;
maxRightPos[j] = (maxRightPos[j + 1] + L[j] > 0) ? maxRightPos[j + 1] + L[j] : 0;
}
for (int i = 0; i < L.size() - 1; ++i) {
tmp = (i < L.size() - 1) ?
std::max(maxLeftPos[i] - maxRightNeg[i + 1], maxRightPos[i + 1] - maxLeftNeg[i])
: std::max(maxLeftPos[i], - maxLeftNeg[i]);
maxDiff = std::max(tmp, maxDiff);
}
return maxDiff;
}

int main(int argc, char **argv) {
int ar[] = {2, -1, -2, 1, -4, 2, 8};
std::vector<int> vec(ar, ar + sizeof(ar) / sizeof(int));
std::cout << computeMaxDiff(vec) << std::endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

This solution in python is short, O(n), I hope this will help u.

``````oo=float('inf')

def find_max_sum(A):
n=len(A)

#to avoid check for final element in for cycle
max_sum=[-oo for i in xrange(n+1)]
tmp_max=-oo
for i in range(n-1,-1,-1):
tmp_max=max(A[i],A[i]+tmp_max)
max_sum[i]=max(max_sum[i],tmp_max)
return max_sum

def solve(A):

right_max,left_max=find_max_sum(A),find_max_sum(A[::-1])
print right_max
negate=lambda x:-1*x
invert= lambda x:map(negate,x)

right_min,left_min=invert(find_max_sum(invert(A))),invert(find_max_sum(invert(A[::-1])))
n=len(A)
maxdiff=-oo
for i in range(n):
if i<n-1:maxdiff=max(maxdiff,abs(left_max[i]-right_min[i+1]),abs(left_min[i]-right_max[i+1]))
return maxdiff

print solve([2,-1 ,-2, 1, -4, 2, 8])
print solve([-1,-2,-3])``````

Comment hidden because of low score. Click to expand.
0

I forgot comments in my code, invert just multiply each element in the array by -1, The idea is to use find_max_sum also to find the minimun sum interval in a[i:].

Comment hidden because of low score. Click to expand.
0

Started throwing some numbers at it. Seems to have some issues.

>>> solve([0, 0, 100, -5, 50])
[145, 145, 145, 45, 50, -inf]
150
>>> solve([0, 0, 100, -5, 50, -1000])
[145, 145, 145, 45, 50, -1000, -inf]
1145
>>> solve([1, 100, -5, 50, -1000])
[146, 145, 45, 50, -1000, -inf]
1145

Comment hidden because of low score. Click to expand.
1
of 1 vote

Am I missing something ? It seems too simple to me :)

``````public static int bestSplit(int[] arr) {
int generalSum = 0;
for (int i : arr)
generalSum += i;

int runningSum = 0;
int bestSplitVal = Math.abs(generalSum);
for (int i = 0; i < arr.length; i++) {
runningSum += arr[i];
if (Math.abs(generalSum - runningSum) > bestSplitVal) {
bestSplitVal = generalSum - runningSum;
}
}
return bestSplitVal;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Will the following solution work?

1. Find maxsubsequence sum M1 (using Kadane's algorithm)
2. Negate the whole array and find again maxSubsequenceSum M2
3. M1 + M2 should be the absolute max difference. [M1 and M2 must be appearing in disjoint contiguous subarrays, for if they overlap, M1 and -M2 cannot be maximum +ve and maximum -ve values respectively]. and we have a proof by contradiction below]

Comment hidden because of low score. Click to expand.
0

dumbo there can be numbers in the subarrays which are common to both hence they can overlap so I dont think it will work

Comment hidden because of low score. Click to expand.
1
of 1 vote

It wont work with the following eg - [4,-1,7] => 1.-> (4,-1,7) 2. -> (1) . But the two subsets overlap

Comment hidden because of low score. Click to expand.
0

@LAP, Nice test case. You are right, the range of minimum sum is completely within the range of maximum sum.
When I checked using my java code below, the solution I proposed is working fine for the data given in the example. However, I need to think more about your test case.

``````import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MaxAbsoluteDiff {

static ArrayList<Integer> numbers = new ArrayList<Integer>();
static ArrayList<Integer> negnumbers = new ArrayList<Integer>();

Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System
.getProperty("line.separator") + "|\\s");
scanner.useDelimiter(delimiters);
int i;
while (scanner.hasNextInt()) {
i = scanner.nextInt();
}
}

int maxsumgbl = 0;
int maxsumrunning = 0;
int j = 0;

for (; j < numbers.size(); j++) {
maxsumrunning += numbers.get(j);

if (maxsumgbl < maxsumrunning) {
maxsumgbl = maxsumrunning;
}

if (maxsumrunning < 0) {
maxsumrunning = 0;
}
}
return maxsumgbl;
}

public static void main(String[] args) {
MaxAbsoluteDiff maxsss = new MaxAbsoluteDiff();
System.out.println("maxsum=" + maxSum);
System.out.println("minsum=" + minSum);
System.out.println("Abs Diff=" + (maxSum - minSum));

}
}``````

Comment hidden because of low score. Click to expand.
1

@LAP, I think the degenerate cases of the minimum sum completely contained in the maximum sum or the maximum sum completely contained in the minimum sum can be handled separately.

Suppose Min is completely contained in Maximum subsum, the the maximum subsum would appear something like

P1 + N + P2, Where P1 is the +ve sum that is to the left of the the minimum sum M and P2 is the +ve sum that is to the right of N.

If P1 > P2 then |P1-N| should give the max absolute diff else it would be |P2-N|

if max subsum is completely contained in min subsum, then the min subsum would appear as

N1 + P + N2. Where N1 is the -ve sum that is to the left of the the maximum sum P and N2 is the -ve sum that is to the right of P.

if N1 > N2 then |N1-P| should be the maximum sum else |N2-P|

The min and max subsums can't overlap, for if they overlap, you can arrive at a proof by contradiction by splitting the sum of numbers into three parts: N + O + M
Where N is the sum of the minimum subset excluding the overlapping part.
O is the sum of the overlapping part
S is the sum of the maximum subset excluding the overlapping part

For N+O to be minimum O has to be -ve
M + O to be maximum O has to be +ve, a contradiction.

Comment hidden because of low score. Click to expand.
0

Can you give you a proof to the above explanation?

It seems valid, but I'm unable to prove it.

Comment hidden because of low score. Click to expand.
0

Your solution is wrong when minimum subarray is contained in the maximum subarray.
Eg : 201, -100, 200, -99
Maximum subarray is 201 + -100 + 200 = 301
Minimum subarray is -100
According to solution is max(201, 200)-(-100) = 301
But, consider subarray as 201, -100, 200 and the other subarray as -99
Answer would be 301-(-99) = 400

Comment hidden because of low score. Click to expand.
0
of 0 vote

He is expecting O(n) time algorithm

Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Find the max continues sum
2. Find the continues min sum
3. return 1-2

``````public static int findMaxDiff(int[] a) {
int maxsum = 0;
int maxEndingHere = 0;

boolean wholeArray = true;
for (int i = 0; i < a.length; i++) {
maxEndingHere = Math.max(maxEndingHere + a[i], 0);

if (maxEndingHere == 0) wholeArray = false;

maxsum = Math.max(maxsum, maxEndingHere);
}
if (wholeArray) return maxsum;

int minsum = 0;
int minEndingHere = 0;
for (int i = 0; i < a.length; i++) {
minEndingHere = Math.min(minEndingHere + a[i], 0);

minsum = Math.min(minsum, minEndingHere);
}

return maxsum - minsum;
}``````

Running time is O(n).

Comment hidden because of low score. Click to expand.
0

Making same mistake as others: [4, -1, 7]

Comment hidden because of low score. Click to expand.
0

Correct. I missed that edge case. I updated the code, how about now? the code above will return 10 for [4,-1,7]

Comment hidden because of low score. Click to expand.
0

Does not work for [2,-1,-2,12,453,-9,2,8]

Comment hidden because of low score. Click to expand.
0

this is not disjoint

Comment hidden because of low score. Click to expand.
0
of 0 vote

Must the two subarrays be adjacent? Yes, because the part "in between", unless it is 0, can contribute to either subarray, making it more optimal.

If so, then let's find a split point defining subarrays A[0,i] and A[i+1,n], such that the maximal subarrays (spanning together over whole A) give the optimal absolute difference of sums, that can be easily done O(n).

Now, here comes an interesting bit. You can prove that the optimal global solution are possibly trimmed subarrays found in the first step. In other words, you cannot find the global optimal solution by trimming subarrays, which do not optimize the first step criterion.

And so, without further ado, to find the optimum solution we have to possibly trim one or both of the subarrays, or "expanding" subarrays starting from one-element subarrays on the left hand side and right hand side of a split point found in the first step, and this is done in O(n).

So final time complexity O(n), space complexity O(1).

Comment hidden because of low score. Click to expand.
0

can u give an example where an element is making both the subsets optimal?

Comment hidden because of low score. Click to expand.
0

won't work for [-6,5,-7,2]. the split point between 5 and -7 won't be found because with out trimming it less than other split points.

Comment hidden because of low score. Click to expand.
0

-4 3 -1 1 2 2 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void main()
{
int a[]={2,-1,-2,1,-4,2,8},n=sizeof(a)/sizeof(int),max[n],min[n],max_max,min_min,i=0;
max=min=max_max=min_min=a;
for(i=1;i<n;i++)
{
max[i]=(max[i-1]+a[i])>a[i]?max[i-1]+a[i]:a[i];
max_max=max[i]>max_max?max[i]:max_max;
min[i]=(min[i-1]+a[i])<a[i]?min[i-1]+a[i]:a[i];
min_min=min[i]<min_min?min[i]:min_min;
}
printf("%d\n",max_max-min_min);
}
Is this ok? it will work in O(n). Are we supposed to identify the subsets also or need to print the difference only?

Comment hidden because of low score. Click to expand.
0

@Anonymous: check for input [4,-1,7]

Comment hidden because of low score. Click to expand.
0

this wont work for [4 -1 7]

Comment hidden because of low score. Click to expand.
0
of 2 vote

An O(n) solution by finding maximum subsequences using Kadane's algorithm

1. Find maxsubsequence sum M1
2. Negate the whole array and find again maxSubsequenceSum M2
3. M1 + M2 should be the absolute max difference. [M1 and M2 must be appearing in disjoint contiguous subarrays, for if they overlap, M1 and -M2 cannot be maximum +ve and maximum -ve values respectively. and we have a proof by contradiction above]
4. Separately handle degenerate cases such as 1) the maximum subsum being contained in the minimum subsum and 2) vice versa

Full working implementation in java is below. Provide Input to the program as:
4 -1 7
-4 1 -7
-9 -4 1 2 -5 -7 -8
9 4 -1 -2 5 7 8

``````import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MaxAbsoluteDiff {

static ArrayList<Integer> numbers = new ArrayList<Integer>();
int pstart = 0, pend = 0, nstart = 0, nend = 0;
int maxpsumgbl = 0, maxnsumgbl = 0, absDiff = 0;

Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System
.getProperty("line.separator") + "|\\s");
scanner.useDelimiter(delimiters);
int i;
while (scanner.hasNextInt()) {
i = scanner.nextInt();
}
}

int maxpsumrunning = 0, maxnsumrunning = 0;
int j = 0;

for (; j < numbers.size(); j++) {
maxpsumrunning += numbers.get(j);
maxnsumrunning += -numbers.get(j);

if (maxpsumgbl < maxpsumrunning) {
maxpsumgbl = maxpsumrunning;
pend = j;
}

if (maxpsumrunning < 0) {
maxpsumrunning = 0;
if (j + 1 < numbers.size() && numbers.get(j + 1) > 0)
pstart = j + 1;
}

if (maxnsumgbl < maxnsumrunning) {
maxnsumgbl = maxnsumrunning;
nend = j;
}

if (maxnsumrunning < 0) {
maxnsumrunning = 0;
if (j + 1 < numbers.size() && -numbers.get(j + 1) > 0)
nstart = j + 1;
}
}

if (nstart > pstart && nend < pend) {
int subsum = 0;
for (int k = pstart; k < nstart; k++) {
subsum += numbers.get(k);
}

if ((maxpsumgbl + maxnsumgbl - subsum) > subsum) {
maxpsumgbl = maxpsumgbl + maxnsumgbl - subsum;
} else {
maxpsumgbl = subsum;
}

} else if (pstart > nstart && pend < nend) {

int subsum = 0;
for (int k = nstart; k < pstart; k++) {
subsum += -numbers.get(k);
}

if ((maxnsumgbl + maxpsumgbl - subsum) > subsum) {
maxnsumgbl = maxnsumgbl + maxpsumgbl - subsum;
} else {
maxnsumgbl = subsum;
}
}
absDiff = maxpsumgbl + maxnsumgbl;
}

public static void main(String[] args) {
MaxAbsoluteDiff maxsss = new MaxAbsoluteDiff();
System.out.println("Max Abs Diff=" + maxsss.absDiff);

}
}``````

Comment hidden because of low score. Click to expand.
0

doesnt work for 1, 2, 3, 4, 5

Comment hidden because of low score. Click to expand.
0

@Anonymous

What result do you expect for this test case?

Comment hidden because of low score. Click to expand.
0

2+3+4+5-1=13

Comment hidden because of low score. Click to expand.
0

Haha. Ain't the difference (2+3+4+5+1) - 0 = 15 greater than 13? Lol.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````main()
{

int a = {2,-1, -2, 1, -4, 2, 8};
int max = a, trackMax = 0;
int min = a, trackMin = 0;
for(int i=1;i<7;i++)
{

trackMax = trackMax + a[i];
trackMin = trackMin + a[i];
if(trackMax < 0) trackMax = trackMax - a[i];
else trackMin = trackMin = trackMin - a[i];
if(trackMax >= max) max = trackMax;
else if (trackMin <= min) min = trackMin;
cout << min << "    " <<max << endl;
}

cout << max-min;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The code for this problem is given below.You can consider the following approach:
a.Find maximum continuous sub-array sum using kadane's algorithm.
b.Similarly find minimum continuous sub-array sum using the same approach.
c.Find the difference between the maximum and minimum element.

``````#include <stdio.h>
#include <stdlib.h>
int maxSumArrayNegative(int arr[],int size)
{
int max_so_far=arr,i;
int max_ending_here=arr;
for(i=1;i<size;i++)
{
max_ending_here=max_ending_here+arr[i];
if(max_so_far<max_ending_here)
{
max_so_far=max_ending_here;
}
}
return max_so_far;
}

int maxSumArrayPositive(int arr[],int size)
{
int max_far=0,i;
int max_ending=0;
for(i=1;i<size;i++)
{
max_ending=max_ending+arr[i];
if(max_ending<0)
{
max_ending=0;
}
if(max_far<max_ending)
{
max_far=max_ending;
}
}
return max_far;
}

int minSumArray(int arr[],int size)
{
int min_so_far=arr;
int min_ending_here=arr,i;
for(i=1;i<size;i++)
{
min_ending_here=min_ending_here+arr[i];
if(min_so_far>min_ending_here)
{
min_so_far=min_ending_here;
}
}
return min_so_far;
}
int main()
{
int arr={-1,-2,-5};
int n=sizeof(arr)/sizeof(arr);
int i,size=0,diff;
for(i=0;i<n;i++)
{
if(arr[i]<0)
size++;
}
if(size==n)
{
int max=maxSumArrayNegative(arr,n);
int min=minSumArray(arr,n);
diff=max-min;

}
else
{
int max=maxSumArrayPositive(arr,n);
int min=minSumArray(arr,n);
diff=max-min;
}
printf("The diff is %d ",diff);
}``````

Comment hidden because of low score. Click to expand.
0

Hi

this wont work for numbers which are all negative
{-1,-3,-5,-2,-1,-4}

Comment hidden because of low score. Click to expand.
0

@DashDash i have edited the code it will work now..

Comment hidden because of low score. Click to expand.
0

I think it will not work for this, try it out
{2, -3, 5}
and is 5 but your maxSumArray will give 4,

Comment hidden because of low score. Click to expand.
0

It is working for every possible case..you can paste it and check it gives 5 not 4..and plzz first test it then you can comment for the correction..

Comment hidden because of low score. Click to expand.
0

For handling with only negative numbers in an array I have added a seperate function for that you can check it..

Comment hidden because of low score. Click to expand.
0

you check your program for : {1,1,-1,-1}
it gives 1, not 4.. :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

So this is what I got, there are no error checking which is obviously bad but I assume we are all coding and making suggestions for valid entries primarily so keep that in mind:

``````public int FindMaxDiff(int[] input, int[] max, int[] min)
{
int maxIndex=0, minIndex=0, leftIndex=0,rightIndex=input.length()-1, midMaxIndex=0, midMinIndex=0, largestSum, smallestSum;
bool isMaxRight;
int[] subArray;

//Find The Min and Max values for the array
//Note that multiple Min and Max values may
//move the index but doesnt change the outcome
for(int probe = 0; probe < input.length()-1; probe++)
{
if(input[maxIndex] < input[probe]) maxIndex = probe;
if(input[minIndex] > input[probe]) minIndex = probe;
}

//Determine if the max value is on the left or right of the minimum value
if(maxIndex > minIndex)
{
isMaxRight = true;
} else
{
isMaxRight = false;
}

if(isMaxRight)
{
//Determine the rightmost index for the max sub array
for(int end = rightIndex; end > maxIndex; end -= 1)
{
subArray = arraycopy(input,maxIndex,end);
int newSum = ArraySum(subArray);
if(largestSum == null)
{
largestSum = newSum;
}
else
{
if(largestSum < newSum)
{
largestSum = newSum;
rightIndex = end;
}
}
}

//Determine the leftmost index for the min sub array
for(int start = 0; start < minIndex; start += 1)
{
subArray = arraycopy(input,start,minIndex);
int newSum = ArraySum(subArray);
if(smallestSum == null)
{
smallestSum = newSum;
}
else
{
if(smallestSum > newSum)
{
smallestSum = newSum;
leftIndex = start;
}
}
}
}
else
{
//Determine the rightmost index for the max sub array
for(int end = rightIndex; end > minIndex; end -= 1)
{
subArray = arraycopy(input,minIndex,end);
int newSum = ArraySum(subArray);
if(smallestSum == null)
{
smallestSum = newSum;
}
else
{
if(smallestSum > newSum)
{
smallestSum = newSum;
rightIndex = end;
}
}
}

//Determine the leftmost index for the min sub array
for(int start = 0; start < maxIndex; start += 1)
{
subArray = arraycopy(input,start,maxIndex);
int newSum = ArraySum(subArray);
if(largestSum == null)
{
largestSum = newSum;
}
else
{
if(largestSum < newSum)
{
largestSum = newSum;
leftIndex = start;
}
}
}
}

//The subArray between the max & min will go to the
//side that it benefits or max if its mutual benefitting
if(isMaxRight)
{
int[] middle = arraycopy(input, minIndex+1, maxIndex-1);
} else
{
int[] middle = arraycopy(input, maxIndex+1, minIndex-1);
}
int midSum = ArraySum(middle);

// The Solution
if(midSum >= 0)
{
if(isMaxRight)
{
max = arraycopy(input, minIndex+1,rightIndex);
min = arraycopy(input, leftIndex, minIndex);
}
else
{
max = arraycopy(input, leftIndex,minIndex-1);
min = arraycopy(input, minIndex, rightIndex);
}
return Math.abs((largestSum + midSum) - smallestSum);
}
else
{
if(isMaxRight)
{
max = arraycopy(input, maxIndex,rightIndex);
min = arraycopy(input, leftIndex, maxIndex-1);
}
else
{
max = arraycopy(input, leftIndex,maxIndex);
min = arraycopy(input, maxIndex+1, rightIndex);
}
return Math.abs(largestSum - (midSum + smallestSum));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution can be found at

Comment hidden because of low score. Click to expand.
0

this does not give right answer for [4 -1 7]

Comment hidden because of low score. Click to expand.
0
of 0 vote

While thinking over this problem I just realized that maximum and minimum subarrays can overlap in only two scenarios:
1) When sum of the common numbers is zero. If sum of common sequence would have been +ve then it would have been part of maximum subarray and not of minimum subarray. Vice verse for -ve sum for common subarray.
2) One subarray is part of other. For example 10, 9, -1, -2, 10 10

Based on the above two possiblilities
1) Find maximum subarray
2) Find minimum subarray
3) If common subarray is zero then it can go either on maximum or minimum side.
4) If one subarray is part of other then find left and right part (non overlapping) of larger subarray and find the difference between this larger part and common elements.

Hence the complexity of this algo is same as finding maximum/minimum subarray problem.

Comment hidden because of low score. Click to expand.
0

4) is not a possibility. The min and max subarrays can either share only 0 as a common boundary or either of them can be present entirely in the other. See my proof by contradiction up in the post.

Comment hidden because of low score. Click to expand.
0

I could not get your point. As I understand, you are saying that point 4 is not correct. You say that max and min subarrays share only 0 as a common boundary or one of them is completely part of other. Even I am saying the same thing as you can see from the example I mentioned previously : 10, 9, -1, -2, 10, 10

Where max subarray is 10, 9, -1, -2, 10, 10
ans min subarray is -1, -2 which is part of max subarray.

If I misunderstood you point please provide me example here.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <algorithm>
using namespace std;
int computMaxDiff(int *array,int len)
{
int *maxarray=new int[len];
int *minarray=new int[len];
maxarray=array;
minarray=-array;
int currentmax=maxarray>0?array:0;
int currentmin=minarray>0?minarray:0;
for(int i=1;i<len;i++)
{
currentmax+=array[i]; //max
maxarray[i]=max(currentmax,maxarray[i-1]);
if(currentmax<0) currentmax=0;

currentmin+=-array[i]; // max of -array
minarray[i]=max(currentmin,minarray[i-1]);
if(currentmin<0) currentmin=0;
}

for (int i=0;i<len;i++) //min of array
minarray[i]=-minarray[i];

int *revmaxarray=new int[len];
int *revminarray=new int[len];
revmaxarray[len-1]=array[len-1];
revminarray[len-1]=-array[len-1];
int revcurrentmax=revmaxarray[len-1]>0?revmaxarray[len-1]:0;
int revcurrentmin=revminarray[len-1]>0?revminarray[len-1]:0;
for(int i=len-2;i>=0;i--)
{
revcurrentmax+=array[i];
revmaxarray[i]=max(revcurrentmax,revmaxarray[i+1]);
if(revcurrentmax<0) revcurrentmax=0;

revcurrentmin+=-array[i];
revminarray[i]=max(revcurrentmin,revminarray[i+1]);
if(revcurrentmin<0) revcurrentmin=0;
}

for (int i=0;i<len;i++)
revminarray[i]=-revminarray[i];

int maxdiff=0;
for (int i=0;i<len;i++)
{
int currMax=max(abs(maxarray[i]-revminarray[i]),abs(minarray[i]-revmaxarray[i]));
if(currMax>maxdiff)
maxdiff=currMax;
}

return maxdiff;
}
int _tmain(int argc, _TCHAR* argv[])
{
int array={-3,4,-1,4,5};
int maxdiff=computMaxDiff(array,5);
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

step 1 : find the sum of whole array. assign it TotalSum O(n)
step 2 : Lets have a few variables SumFromBegining=0, SumFromEnd=TotalSum, MaxDifference=0, MaxDifferenceSplitIndex=0. all these are integers or long ---O(1)
step 3 : Iterate through the array from beginning to end.
for each iteration you need need to do the following
1. add the current array element ie. array[i] to SumFromBegining
2. subtract the current array element ie. array[i] from SumFromEnd
3. Difference=absolute(SumFromEnd-SumFromBegining)
4. if Difference > MaxDifference then MaxDifference=Difference and MaxDifferenceSplitIndex=i

now this process is of O(n)

After the iteration array[0 to MaxDifferenceSplitIndex ] and array[MaxDifferenceSplitIndex+1 to n] are the answer.

this is a solution with O(n)

hope i did not make a mistake..:-)

Comment hidden because of low score. Click to expand.
0
of 0 vote

I've been through all of these solutions and correct me if i'm wrong, but i think absolutely none of them work for all possible cases. There's one or two which work, but they aint 0(n).

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Loler's solution should work in O(n) and for all possible cases if implemented correctly.

The code posted in a comment to that answer was posted by someone else, and I have not verified it. People seem to have found some issues with it. But these are implementation issues, not problems with the idea.

Comment hidden because of low score. Click to expand.
0
of 0 vote

for this problem finding maximum and minimum contiguous don't work. for example consider this two test case:
1)array=[-6, 3, 5, 4, -1, -7, 17, 8]
in this case maxSum=25 and minSum=-8 if we search disjoint contiguous subarray. so the absolute difference is equal 33. however, the max difference is 35 if we separate [-6] and [3, 5, 4, -1, -7, 17, 8]. sum1=-6, sum2=29 so difference is 35.
2)array=[4, -1, 5]
the same above maximum absolute difference between two disjoint contiguous subarray is 6.[-1] and .

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Given an array, find the following max/min continuous array:
- left_min_array: continuous max array
- left_max_array: continuous min array
- right_min_array: reverse the array, calculate the continuous max array, reversed again
- right_max_array: reverse the array, calculate the continuous min array, reversed again
2. Iterate the array, find the maximum among the following four integers:
- abs(left_min_array[i]) + abs(right_min_array[i+1])
- abs(left_min_array[i]) + abs(right_max_array[i+1])
- abs(left_max_array[i]) + abs(right_min_array[i+1])
- abs(left_max_array[i]) + abs(right_max_array[i+1])
And store the largest result in an array, let's call result
3. The maximum difference is the max element in the result array

Code is attached at the end, following are the test cases:
- {2,-1,-2,12,453,-9,2,8}
- {7,-1,4}
- {1,2,3,4,5}
- {-1,-3,-5,-2,-1,-4}

``````public static int[] findMaxOrMin(int[] array,boolean findMax) {
int[] res = new int[array.length];

res = array;
for(int i=1;i<array.length;i++) {
if(findMax)
res[i] = Math.max(res[i-1]+array[i],array[i]);
else
res[i] = Math.min(res[i-1]+array[i],array[i]);
}

return res;
}

public static int[] reverseArray(int[] array) {

for(int i=0;i<array.length/2;i++) {
int temp = array[(array.length-1)-i];
array[(array.length-1)-i] = array[i];
array[i] = temp;
}
return array;
}

public static int findMaxDiff(int[] array) {

int[] left_min_array = findMaxOrMin(array,false);
int[] left_max_array = findMaxOrMin(array,true);
int[] right_min_array = reverseArray(findMaxOrMin(reverseArray(Arrays.copyOfRange(array,0,array.length)),false));
int[] right_max_array = reverseArray(findMaxOrMin(reverseArray(Arrays.copyOfRange(array,0,array.length)),true));

int[] result = new int[array.length-1];
int largestIndex = 0;

for(int i=0;i<result.length;i++) {
int combo1 = Math.abs(left_min_array[i])+Math.abs(right_min_array[i+1]);
int combo2 = Math.abs(left_min_array[i])+Math.abs(right_max_array[i+1]);
int combo3 = Math.abs(left_max_array[i])+Math.abs(right_min_array[i+1]);
int combo4 = Math.abs(left_max_array[i])+Math.abs(right_max_array[i+1]);
result[i] = Math.max(Math.max(Math.max(combo1,combo2),combo3),combo4);
if(i>1)
largestIndex = result[i]>result[i-1] ? i:largestIndex;
}
return result[largestIndex];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

step 1 : find the sum of whole array. assign it TotalSum O(n)
step 2 : Lets have a few variables SumFromBegining=0, SumFromEnd=TotalSum, MaxDifference=0, MaxDifferenceSplitIndex=0. all these are integers or long ---O(1)
step 3 : Iterate through the array from beginning to end.
for each iteration you need need to do the following
1. add the current array element ie. array[i] to SumFromBegining
2. subtract the current array element ie. array[i] from SumFromEnd
3. Difference=absolute(SumFromEnd-SumFromBegining)
4. if Difference > MaxDifference then MaxDifference=Difference and MaxDifferenceSplitIndex=i

now this process is of O(n)

After the iteration array[0 to MaxDifferenceSplitIndex ] and array[MaxDifferenceSplitIndex+1 to n] are the answer.

this is a solution with O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

here's a O(n) solution:

``````// {1, 2, -5, 10, 0, - 15, -1, 3, -4}
// maximize 10 - (-17)) = 27

// let's consider a pointer that moves through the set which breaks set into two
// regions - left and right which are subsets

// for each of these subsets we want to consider max and min values
// and then use the ones that give best possible diff

// following structure keeps track of max and min for a given subset
struct elem {
int maxsum;
int minsum;
int min;
int max;

elem() : maxsum(0), minsum(0), min(0), max(0) {}
elem& operator = (int a) { maxsum = a; minsum = a; min = a; max = a; return *this; }
elem& operator + (int a) { maxsum+=a; if (maxsum < 0) maxsum = 0; if (maxsum > max) max = maxsum;
minsum+=a; if (minsum > 0) minsum = 0; if(minsum < min) min = minsum; return *this; }
};

int maxdiffinsubsets(int A[], int size)
{
elem *DA1 = new elem [size - 1];
elem* DA2 = new elem [size - 1];
int i;
int bestdiff = 0;

// create a dynamic array that stores min and max of all possible subsets
DA1 = A;
for (i = 1; i < size - 1; i++)
{
DA1[i] = DA1[i-1] + A[i];
}

// this second array is the counter part to the first one so for example
// for a set {1, 2, -1 } if DA1 got {1} covered, DA2 will cover {2, -1}

DA2[size-1] = A[size-1];
for (i = size - 2; i >= 0; i--)
{
DA2[i] = DA2[i + 1] + A[i];
}

// find the best combination
for (i = 0; i < size - 1; i++)
{
int temp = max(DA1[i].max - DA2[i].min, DA2[i].max - DA1[i].min);
if (temp > bestdiff)
bestdiff = temp;
}

return bestdiff;
}

int main (int argc, void** argv)
{
int A[] = {4,-1,7}; //{1, 2, 5, -15,5,-2, 1, 0};//{1, 2, -5, 10, 0, - 15, -1, 3, -4};
int size = sizeof(A)/sizeof(int);

cout<<maxdiffinsubsets(A, size)<<endl;
_getch();

}``````

Comment hidden because of low score. Click to expand.
0

finished going through all the posts on here. :) Seems like my implementation is closest to what Loler suggested in C. Only difference is I am using two DA and each maintains structure that keeps track of max and min for the interval.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anybody comment on my approach .
1. find the max sum subsequence using DP. Store the sum and store the subsequence. Replace those elements by INT_MAX.
2. find the min sum subsequence using DP. store the sum and subsequence
3. Now calculate the difference, and print those sets.
I think there is no way this subsets will overlap.

This is O(n) solution since steps 2 and 3 takes O(n) in DP.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int get_index(vector<int>& a)
{
int n = a.size();
if (n <=1 ) return -1;
vector<long long int> prefix_sum(n, 0);
prefix_sum = a;
for (int i=1; i < n; i++) prefix_sum[i] += prefix_sum[i-1];
long long int min_diff min_idx(-1);
for (int i=0; i < n-1; i++)
{
long long  int diff = abs( prefix_sum[i] - prefix_sum[n-1] + prefix_sum[i+1] );
if (min_idx == -1 || diff < min_diff) { min_diff = diff; min_idx = i; }
}
return min_idx ;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````List<int> maxArray = new List<int>();
List<int> minArray = new List<int>();
List<int> currentRun = new List<int>();

int currentRunCount = 0;
int max = 0;
int min = 0;
for (int i = 0; i < array.Length; i++)
{
currentRunCount += array[i];

if (currentRunCount > 0)
{
if (currentRunCount >= max)
{
if (maxArray.Count == 0 || maxArray.ElementAt(maxArray.Count - 1) == currentRun.ElementAt(0) - 1)
{
}
else
{
maxArray = currentRun;
}

max = currentRunCount;
currentRunCount = 0;
currentRun = new List<int>();
}
}

if (currentRunCount < 0)
{
if (currentRunCount <= min)
{
if (minArray.Count == 0 || minArray.ElementAt(minArray.Count - 1) == currentRun.ElementAt(0) - 1)
{
}
else
{
minArray = currentRun;
}

min = currentRunCount;
currentRunCount = 0;
currentRun = new List<int>();
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I came across this problem and thought about this and came up with the possible solution. I am unable to find cases in order to fail this solution. Can someone please enumerate a set for the same?

My algorithm:

1.Calculate the continuous sum of all elements while going from 1 to n and store them in an array . Do the same while going from n to 1
2. In the first array mark a point which has minimum value and which has maximum value
. Do the same for the second array
3. Check for four scenarios.
a) Break array just after array 1 has hit a minimum value
b) Break array just before array 1 has hit a max value
c) Break array just before array 2 has hit a minimum value
d) Break array just after array 2 has hit a max value
4. Max of (a,b,c,d) from above is the answer

Example:
Array : 10,1,3,-10,2

Array 1: 10,11,14,4,6 Max: 14 Min: 4
Array 2: 6,-4,-5,-8,2 Max: 6 Min: -8
a) Break after Min:4 i.e Break after -10 in Array . Absolute Diff is 2
b) Break before Max:14 i.e Break before 3 in Array . Absolute Diff is 16
c) Break after Max:6 i.e Break after 10 in Array . Absolute Diff is 14
d) Break before Min: -8 i.e Break before -10 in Array . Absolute diff is 22

Max(a,b,c,d) = 22

Solution complexity is O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

I came across this problem and thought about this and came up with the possible solution. I am unable to find cases in order to fail this solution. Can someone please enumerate a set for the same?

My algorithm:

1.Calculate the continuous sum of all elements while going from 1 to n and store them in an array . Do the same while going from n to 1
2. In the first array mark a point which has minimum value and which has maximum value
. Do the same for the second array
3. Check for four scenarios.
a) Break array just after array 1 has hit a minimum value
b) Break array just before array 1 has hit a max value
c) Break array just before array 2 has hit a minimum value
d) Break array just after array 2 has hit a max value
4. Max of (a,b,c,d) from above is the answer

Example:
Array : 10,1,3,-10,2

Array 1: 10,11,14,4,6 Max: 14 Min: 4
Array 2: 6,-4,-5,-8,2 Max: 6 Min: -8
a) Break after Min:4 i.e Break after -10 in Array . Absolute Diff is 2
b) Break before Max:14 i.e Break before 3 in Array . Absolute Diff is 16
c) Break after Max:6 i.e Break after 10 in Array . Absolute Diff is 14
d) Break before Min: -8 i.e Break before -10 in Array . Absolute diff is 22

Max(a,b,c,d) = 22

Solution complexity is O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think Loler is right, the algorithm could be implemented in O(n), and here is my code:

``````#include <iostream>
#include <vector>

void max_sum_diff( int a[], int n ) // time Complexity: O(n)
{
std::vector<int> pmax(n,0), //max contiguous sum end with a[i]
pmin(n,0), //min contiguous sum end with a[i]
smax(n,0), //max contiguous sum begin with a[i]
smin(n,0); //min contiguous sum begin with a[i]

int sum = a;
pmax = pmin = a;
for( int i = 1; i <= n-1; ++i )
{
pmax[i] = std::max( pmax[i-1] + a[i], a[i] );
pmin[i] = std::min( pmin[i-1] + a[i], a[i] );
sum += a[i];
}

smax[n-1] = smin[n-1] = a[n-1];
for( int i = n-2; i >=0; --i )
{
smax[i] = std::max( smax[i+1] + a[i], a[i] );
smin[i] = std::min( smin[i+1] + a[i], a[i] );
}

//change pmax has the max sum in range[0,i], smax has the max sum in range[i,n-1]
//so is pmin and smin
for( int i = 1; i <= n-1; ++i )
{
pmax[i] = std::max( pmax[i-1], pmax[i] );
pmin[i] = std::min( pmin[i-1], pmin[i] );
}

for( int i = n-2; i >= 0; --i )
{
smax[i] = std::max( smax[i+1], smax[i] );
smin[i] = std::min( smin[i+1], smin[i] );
}

int diff1, diff2, max_diff = abs(sum);
for( int i = 0; i <= n - 2; ++i )
{
diff1 = abs( pmax[i] - smin[i+1] );
diff2 = abs( pmin[i] - smax[i+1] );
max_diff = std::max( diff1, max_diff );
max_diff = std::max( diff2, max_diff );
}

std::cout << "Max Diff: " << max_diff << std::endl;
}

int main( int argc, char* argv[] )
{
int a[] = { 2, -1, -2, 1, -4, 2, 8 };
max_sum_diff( a, 7 );

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

i am assuming the minimum sum of a sub array is negative or empty.
and that the maximum sum of a sub array is positive or empty.
the problem can be defined as follow:
1. Find the max sub sum
2. Find the min sub sum

if they do not intersect return their difference; otherwise check if the min sub sum is starting after the max sub sum:

[maxSubSumStart ---------- minSubSumStart ----------------MinSubSumEnd--------maxSubSumEnd]

I want to prove that if intersection is not allowed then either the left max sub sum or the right sub sum is the largest sub sum.
In this case each side of minSubSumArray is larger than the absolute value of minSubSumArray (otherwise their sum is below 0 and we would have taken only one part).
assume the left sub array is the bigger one.
That implies that it is also the biggest sub array in the array (because any other max sub array that wasn't added to the current max array, wasn't added because it is smaller (absolute value)than some minimum sub array, and therefore it is smaller then the minimum sub array and therefor smaller then the left and right parts of the maxsub array.

Therefore the result would be: max sub is the left side of the max array, and the min sub is the minimum sub array.

the same logic is true also in case the max array start in the middle of the min array

this is the code , i still need to do some re-factoring and also I might have some indexing issues:

``````static void PrintMaxDifferanceArray(int[] arr)
{
int max = 0;
int tempMax = 0;
int tempMaxStart =0;
int maxStart =0;
int maxEnd =0;

int min = 0;
int tempMin = 0;
int tempMinStart = 0;
int minStart = 0;
int minEnd = 0;

for (int i = 0; i < arr.Length; i++ )
{
if (tempMin + arr[i] > 0)
{
tempMin = 0;
tempMinStart = i + 1;
}
else
{
tempMin += arr[i];
}

if (tempMin < min)
{
min = tempMin;
minStart = tempMinStart;
minEnd = i;
}
if (tempMax + arr[i] < 0)
{
tempMax = 0;
tempMaxStart = i + 1;
}
else
{
tempMax += arr[i];
}

if (tempMax > max)
{
max = tempMax;
maxStart = tempMaxStart;
maxEnd = i;
}
}
//The maximum sub array starts in the middle of the min sub array.
//minStart------------maxStart-----------------minEnd
if (maxStart >= minStart && maxStart <= minEnd)
{
int leftSum =0;
//take the left part of the min array. from min start to max start
arr.ToList().Skip(minStart).Take(maxStart - minStart).ToList().ForEach(x => leftSum += x);

//take the right part of the min array. from max end to min end
int rightSum = 0;
if(maxEnd<minEnd)
arr.ToList().Skip(maxEnd + 1).Take(minEnd - maxEnd).ToList().ForEach(x => rightSum += x);

if (leftSum < rightSum)
{
Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}",minStart,maxStart-1,maxStart,maxEnd);
Console.WriteLine("the difference is {0}", max-leftSum);
}
else
{
Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", maxEnd+1, minEnd, maxStart, maxEnd);
Console.WriteLine("the difference is {0}", max - rightSum);
}
return;
}
//The minimum sub array starts in the middle of the max sub array.
//maxStart------------minStart-----------------maxEnd
if (minStart >= maxStart && minStart <= maxEnd)
{
int leftSum = 0;
//take the left part of the max array. from max start to min start
//maxStart------------minStart
arr.ToList().Skip(maxStart).Take(minStart - maxStart).ToList().ForEach(x => leftSum += x);

//take the right part of the max array. from min end to max end
int rightSum = 0;
//minEnd+1------------maxEnd
if (minEnd < maxEnd)
arr.ToList().Skip(minEnd + 1).Take(maxEnd - minEnd).ToList().ForEach(x => rightSum += x);
if (leftSum > rightSum)
{
Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", maxStart, minStart - 1, minStart, minEnd);
Console.WriteLine("the difference is {0}", leftSum-min);
}
else
{
Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", minStart, minEnd, minEnd+1, maxEnd);
Console.WriteLine("the difference is {0}", rightSum - min);
}
return;
}

//no intersection
Console.WriteLine("Solution is: startMin = {0}, endMin = {1}.  startMax = {2}, endMax = {3}", minStart, minEnd, maxStart, maxEnd);
Console.WriteLine("the difference is {0}", max - min);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find the cumulative sum for 0<=i<n and store sum in cumulative[ ]
2. Find j, such that abs(cumulative[ j ] - cumulative [n-1]) is maximum
3. 0 to j is one subarray and j+1 to n-1 is the other subarray

Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution should work for cases:
1 - compute kadane as follow: var kadane = function (arr, k, j, isMin)
which should return min/max sum (according to isMin flag) for the arr elements starting at k index and end (inclusive) at j index.
return value should be an object that includes the sum, start index, end index.
2 - find max when k==0 and j==arr.length-1. let's call it MAX and assume it has startIndex==si and endIndex==ei;
3 - find min when k==0 and j==arr.length-1. let's call it MIN and assume it has startIndex==si and endIndex==ei;
4 - for the output of 2 MAX - find min on the right side of it using k==MIN.endIndex+1 and j==arr.length and on the left side of it using k==0 and j==MIN.startIndex-1 (if possible and out of arr indexes).
5 - do the as in 4 step for the MIN (find max on both sides of it).
6 - out of the result in 4 and 5 take the highest and lowest among the two and calculate the range of them with MAX and MIN respectively.
7 - among the two pairs from step 6 - MIN and a max on its left/right and MAX and a min on its left/right choose the pair with the higher range and return it.

``````var Range = function (s, e, sum, isMin) {
this.sum = sum;
this.s = s;
this.e = e;
this.isMin = isMin;
};

var kadane = function (arr, k, j, isMin) {
var mSoFar = arr[k];
var mEndHere = arr[k];
var s = k;
var e = k;
var st = k;
var i = k+1;
var cur;

for(; i < j+1; i++){
cur = arr[i];
if((isMin && (mEndHere > 0)) || (!isMin && (mEndHere < 0))) {
mEndHere = cur;
st = i;
}
else{
mEndHere += cur;
}

if((isMin && (mEndHere < mSoFar)) || (!isMin && (mEndHere > mSoFar))){
mSoFar = mEndHere;
e = i;
s = st;
}
}

return new Range (s, e, mSoFar, isMin);

};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If there are 2 elements in the array, or all the elements are zero, the
solution is really trivial. If there are less than 2 elements, there is no
solution.

If all the numbers are non-negative, the problem is completely different from
if you have both signs, all positive is somewhat easier. The smaller sub-array
will contain only 1 element, and the larger subarray will contain either the
front or the back. Start with the front of the array being the 'large' value
and the second item being 'small', we store this as our 'current optimum'. Now
add the 2nd item to 'large' and call the next element 'small'; if this is
better than our first solution, we store it as our current optimum. We go
through the array forwards the whole way through, then we do the same thing
going backwards. The optimal solution we find after both passes is the optimal
solution. This solves in order n (3 passes through n elements). The same logic
works if all the elements are 0 or negative.

If we have both positive and negative numbers, create a 2nd array (partioned
array) 'partitioning' every positive and negative sequence: 2 -1 -2 1 -4 2 8
becomes  [-3]  [-4] . I am pretty sure this is the right direction,
but from here on out, I bet someone (possibly me with more time) comes up with
something better than I have following.

Now create yet another array combining all the negative elements if and only if
their sum is less than the number between them. Repeat this process until you
cannot. So you get [-6] in this example. Now create yet another array doing
this with the positive values, giving you . The largest of the
positive and smallest negative are the solution if we can ignore the
requirement the arrays do not overlap, and the solution if they do not overlap.
So far, we've done nothing beyond order n. If they overlap, we can find a
place to split the segment that overlaps fairly easily, and this is almost
always the correct solution, but you can come up with examples where it is not.
I think going back to our partioned array and finding other combinations is the
trick, but cannot think of better than n^2 way to do that.

Of course, you need to store a bit more to go back and find the array indexes,
but that is trivial so I left it out.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Based upon comments above, I have written following code.

{
public class DisjointSubarraysLinearTime {
public static void main(String[] args) {
int[] input = {2, -1, -2, 1, -4, 2, 8};
System.out.println("diff: " + getDifference(input));
}
public static int getDifference(int[] a) {
int[] MAX = new int[a.length];
int[] MIN = new int[a.length];
int result = Integer.MIN_VALUE;
setMinMaxArrays(a, MIN, MAX);
for (int i = 0; i < a.length-1; i++) {
result = Math.max(result, Math.abs(MAX[i] - MIN[i+1]));
}
for (int i = 0; i < a.length; i++) {
a[i] = -a[i];
}
setMinMaxArrays(a, MIN, MAX);
for (int i = 0; i < a.length-1; i++) {
result = Math.max(result, Math.abs(MAX[i] - MIN[i+1]));
}
return result;
}
public static void setMinMaxArrays(int[] a, int[] MIN, int[] MAX) {
MAX = a;
int maxEndingHere = a;
for (int i = 1; i < a.length; i++) {
if (maxEndingHere < 0) {
maxEndingHere = a[i];
}
else {
maxEndingHere += a[i];
}
MAX[i] = Math.max(maxEndingHere, MAX[i-1]);
}
MIN[a.length-1] = a[a.length-1];
int minEndingHere = a[a.length-1];
for (int i = a.length - 2; i >= 0; i--) {
if (minEndingHere > 0) {
minEndingHere = a[i];
}
else {
minEndingHere += a[i];
}
MIN[i] = Math.min(minEndingHere, MIN[i+1]);
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Based upon comments above, I have written following code(formatted):

``````public class DisjointSubarraysLinearTime {
public static void main(String[] args) {
int[] input = {2, -1, -2, 1, -4, 2, 8};
System.out.println("diff: " + getDifference(input));
}
public static int getDifference(int[] a) {
int[] MAX = new int[a.length];
int[] MIN = new int[a.length];
int result = Integer.MIN_VALUE;
setMinMaxArrays(a, MIN, MAX);
for (int i = 0; i < a.length-1; i++) {
result = Math.max(result,  Math.abs(MAX[i] - MIN[i+1]));
}
for (int i = 0; i < a.length; i++) {
a[i] = -a[i];
}
setMinMaxArrays(a, MIN, MAX);
for (int i = 0; i < a.length-1; i++) {
result = Math.max(result,  Math.abs(MAX[i] - MIN[i+1]));
}
return result;
}
public static void setMinMaxArrays(int[] a, int[] MIN, int[] MAX) {
MAX = a;
int maxEndingHere = a;
for (int i = 1; i < a.length; i++) {
if (maxEndingHere < 0) {
maxEndingHere = a[i];
}
else {
maxEndingHere += a[i];
}
MAX[i] = Math.max(maxEndingHere, MAX[i-1]);
}
MIN[a.length-1] = a[a.length-1];
int minEndingHere = a[a.length-1];
for (int i = a.length - 2; i >= 0; i--) {
if (minEndingHere > 0) {
minEndingHere = a[i];
}
else {
minEndingHere += a[i];
}
MIN[i] = Math.min(minEndingHere, MIN[i+1]);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I won't prove it, but it's true that you can find the max or min subsequence of an array in O(n) time and space.

Assuming that's true, compute the max and min subarrays. If they don't overlap, then you have your answer.

What if they do overlap?

If they overlap in the middle (e.g. [1, 5], [3, 10] overlap at [3, 5]), observe that if we remove the overlapping part from both (max and min) subarrays, that that will not change the absolute value of the difference of their sums.

WLOG, assume the min sequence contains the max sequence. Then, our disjoint max sequence will be *the* max sequence, and our disjoint min sequence will be either the left or right part that borders the inner max--return the side with smaller (more negative) sum.

It's a bit more involved to prove that the smaller side of the containing subsequence will still be the right one, but if you try and fail to find a counterexample, you'll see why.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#define maxn 100000

int l[maxn];
int r[maxn];

int work(vector<int> a) {
int n = a.size();
l = a;
for (int i=1;i<n;i++)
l[i] = max(a[i],l[i-1]+a[i]);
for (int i=1;i<n;i++)
l[i] = max(l[i-1],l[i]);
r[n-1] = a[n-1];
for (int i=n-2;i>-1;i--)
r[i] = min(a[i],r[i+1]+a[i]);
for (int i=n-2;i>-1;i--)
r[i] = min(r[i],r[i+1]);
int ans = 0;
for (int i=0;i<n-1;i++)
ans = max(ans,l[i]-r[i+1]);
return ans;
}

int maxdifference(vector<int> a) {
int ans = 0;
ans = max(ans,work(a));
for (int i=0;i<a.size();i++) a[i] = -a[i];
ans = max(ans,work(a));
return ans;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution in python is short, O(n), I hope this will help u.

``````oo=float('inf')

def find_max_sum(A):
n=len(A)

#to avoid check for final element in for cycle
max_sum=[-oo for i in xrange(n+1)]
tmp_max=-oo
for i in range(n-1,-1,-1):
tmp_max=max(A[i],A[i]+tmp_max)
max_sum[i]=max(max_sum[i],tmp_max)
return max_sum

def solve(A):

right_max,left_max=find_max_sum(A),find_max_sum(A[::-1])
print right_max
negate=lambda x:-1*x
invert= lambda x:map(negate,x)

right_min,left_min=invert(find_max_sum(invert(A))),invert(find_max_sum(invert(A[::-1])))
n=len(A)
maxdiff=-oo
for i in range(n):
if i<n-1:maxdiff=max(maxdiff,abs(left_max[i]-right_min[i+1]),abs(left_min[i]-right_max[i+1]))
return maxdiff

print solve([2,-1 ,-2, 1, -4, 2, 8])
print solve([-1,-2,-3])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int main()
{

//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n,i,j;
int dp1,dp2,a;
//memset(dp1,0,sizeof(dp1));
cin>>n;
for(i=0;i<n;i++){cin>>a[i];}
dp1=a;
dp1=a;
for(i=1;i<n;i++)
{
dp1[i]=min(a[i],a[i]+dp1[i-1]);
dp1[i]=max(a[i],a[i]+dp1[i-1]);
}
dp2[n-1]=a[n-1];
dp2[n-1]=a[n-1];
for(i=n-2;i>=0;i--)
{
dp2[i]=min(a[i],a[i]+dp2[i+1]);
dp2[i]=max(a[i],a[i]+dp2[i+1]);
}
int ans=0,p,q,r,s;
for(i=0;i<n-1;i++)
{
p=abs(dp1[i]-dp2[i+1]);
p=max(p,abs(dp1[i]-dp2[i+1]));
p=max(p,abs(dp1[i]-dp2[i+1]));
p=max(p,abs(dp1[i]-dp2[i+1]));
if(p>ans)
{
q=i;ans=p;
}
}
cout<<q<<" "<<ans<<"\n";
return 0;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution is similar to "Best Time to Buy and Sell Stock III" in leetcode.

Comment hidden because of low score. Click to expand.
0
of 0 vote

MaxLR[] = maximum subarray sum at each position of the input array going left to right. O(n)
MinLR[] = minimum subarray sum at each position of the input array going left to right. O(n)
MaxRL[] = maximum subarray sum at each position of the input array going right to left. O(n)
MinRL[] = minimum subarray sum at each position of the input array going right to left. O(n)
Then for each position i, get the currentMaxdifference by getting the greatest difference between the maximum left-to-right at pos i and the minimum right-to-left at position i+1 (MaxLR[i]-MinRL[i+1]), and the minimum left-to-right at pos i and the maximum right-to-left at pos i+1 (MaxRL[i+1]-MinLR[i]). If the current max diff is greater than the general MaxDiff change maxDiff to currentMaxDiff.

Here is the code that implement this solution, you can use genArray to generate a random array and printArray to print it.

``````public class DisjointSubarraysDifference {
public static int maxDiffSubArrays(int[] a) {
// Compute max left -> right
int[] maxlr = new int[a.length];
maxlr = a;
for(int i=1;i<a.length;i++) {
maxlr[i] = (maxlr[i-1]+a[i]>a[i])?maxlr[i-1]+a[i]:a[i];
}
// Compute min left -> right
int[] minlr = new int[a.length];
minlr = a;
for(int i=1;i<a.length;i++) {
minlr[i] = (minlr[i-1]+a[i]<a[i])?minlr[i-1]+a[i]:a[i];
}
// Compute max right -> left
int[] maxrl = new int[a.length];
maxrl[a.length-1] = a[a.length-1];
for(int i=a.length-2;i>=0;i--) {
maxrl[i] = (maxrl[i+1]+a[i]>a[i])?maxrl[i+1]+a[i]:a[i];
}
// Compute min right -> left
int[] minrl = new int[a.length];
minrl[a.length-1] = a[a.length-1];
for(int i = a.length-2;i>=0;i--) {
minrl[i] = (minrl[i+1]+a[i]<a[i])?minrl[i+1]+a[i]:a[i];
}
int maxDiff = 0;
int currDiff = 0;
for(int i=0;i<a.length-1;i++) {
currDiff = Math.max((maxlr[i]-minrl[i+1]),(maxrl[i+1]-minlr[i]));
if(currDiff>maxDiff) {
//System.out.println("New Breaking Point: "+i);
maxDiff=currDiff;
}
}
return maxDiff;
}
public static int[] genArray(int n) {
Random r = new Random();
int[] a = new int[n];
for(int i=0;i<n;i++) {
a[i] = r.nextInt(10)-4;
}
return a;
}
public static void printArray(int[] a) {
for(int i=0;i<a.length-1;i++) {
System.out.print(a[i]+",");
}
System.out.println(a[a.length-1]);
}
public static void main(String[] args) {
int[] a = genArray(10);
printArray(a);
int maxDiff = maxDiffSubArrays(a);
System.out.println("MaxDiff "+maxDiff);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class CareerCup_19286747{
public static void main(String[]args){
int[][] arrs = new int[][]{
{2,-1,-2,12,453,-9,2,8}
,{7,-1,4}
,{1,2,3,4,5}
,{-1,-3,-5,-2,-1,-4}
,{2, -1, -2, 1, -4, 2, 8}
};
for(int[] arr : arrs){
Range[] ranges = findRanges(arr);
print(arr, ranges, ranges);
}
}
static Range[] findRanges(int[] arr){
Range[] minSumsFromLeft = findMinSumsFromLeft(arr);
Range[] maxSumsFromRight = findMaxSumsFromRight(arr);
int i = findOptimalSplit(minSumsFromLeft, maxSumsFromRight);

Range[] maxSumsFromLeft = findMaxSumsFromLeft(arr);
Range[] minSumsFromRight = findMinSumsFromRight(arr);
int j = findOptimalSplit(maxSumsFromLeft, minSumsFromRight);

int diff1 = optimalValAtSplit(i, minSumsFromLeft, maxSumsFromRight);
int diff2 = optimalValAtSplit(j, maxSumsFromLeft, minSumsFromRight);
if (diff1 > diff2){
return optimalRangesAtSplit(i, minSumsFromLeft, maxSumsFromRight);
} else {
return optimalRangesAtSplit(j, maxSumsFromLeft, minSumsFromRight);
}
}
static Range[] optimalRangesAtSplit(int i, Range[] leftSums, Range[] rightSums){
return new Range[]{leftSums[i], rightSums[i+1] };
}
static int optimalValAtSplit(int i, Range[] leftSums, Range[] rightSums){
return Math.abs(rightSums[i+1].sum - leftSums[i].sum);

}
static int findOptimalSplit(Range[] leftSums, Range[] rightSums){
int maxVal = Integer.MIN_VALUE;
int ans = -1;
for(int i = 0; i < leftSums.length; ++i){
int nextVal = optimalValAtSplit(i, leftSums, rightSums);
if (maxVal < nextVal){
maxVal = nextVal;
ans = i;
}
}
return ans;
}
static Comparator<Integer> NATURAL_ORDER = new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return Integer.compare(a,b);
}
};
static Comparator<Integer> REVERSED_ORDER = Collections.reverseOrder(NATURAL_ORDER);
static Range[] findMinSumsFromLeft(int[] arr){
return findSumsFromLeft(arr, REVERSED_ORDER);
}
static Range[] findMaxSumsFromLeft(int[] arr){
return findSumsFromLeft(arr, NATURAL_ORDER);
}
static Range[] findSumsFromLeft(int[] arr, Comparator<Integer> comparator){
Range[] ans = new Range[arr.length-1];
for(int i = 0, s = i, sum = 0; i < ans.length; ++i){
sum += arr[i];
if (comparator.compare(arr[i], sum)<0){
sum = arr[i];
s = i;
}
ans[i] = new Range(s, i, sum);
}
return ans;
}
static Range[] findMinSumsFromRight(int[] arr){
return findSumsFromRight(arr, REVERSED_ORDER);
}
static Range[] findMaxSumsFromRight(int[] arr){
return findSumsFromRight(arr, NATURAL_ORDER);
}
static Range[] findSumsFromRight(int[] arr, Comparator<Integer> comparator){
Range[] ans = new Range[arr.length];
for(int i = arr.length-1, e = i, sum = 0; i > 0; --i){
if (comparator.compare(arr[i], sum)<0){
sum = arr[i];
e = i;
}
ans[i] = new Range(i, e, sum);
}
return ans;
}
static void print(int[] arr, Range left, Range right){
print(arr, left);
System.out.print(" ");
print(arr, right);
System.out.println();
}
static void print(int[] arr, Range r){
System.out.print("[");
System.out.print(arr[r.start]);
for(int i = r.start+1; i <= r.end; ++i){
System.out.printf(", %d", arr[i]);
}
System.out.print("]");
}
}
class Range{
int start, end, sum;
Range(int start, int end, int sum){
this.start = start;
this.end = end;
this.sum = sum;
}
public String toString(){
return String.format("[%d,%d] sum:%d", start, end, sum);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code

``````import sys
from math import fabs
input = [2, -1, -2, 1, -4, 2, 8]
n = len(input)

start = 0
maxSum = -sys.maxsize - 1
firstArray = []
secondArray = []

while start < n - 1:
subLength = 1
while (start + subLength) < n:
first = input[start:(start + subLength)]
second = input[(start + subLength):]
subLength += 1

firstSum = 0
for element in first:
firstSum += element

secondSum = 0
for element in second:
secondSum += element
if fabs(firstSum - secondSum) > maxSum:
maxSum = fabs(secondSum - firstSum)
firstArray = first
secondArray = second
start += 1

print(firstArray, secondArray)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MaxDiff {
public static int computeMaxDiff(int[] arg) {
int[] maxForward = helper(arg, true, true);
int[] minForward = helper(arg, false, true);
int[] maxReverse = helper(arg, true, false);
int[] minReverse = helper(arg, false, false);
int result = Math.max(Math.abs(minReverse), Math.abs(maxReverse));
for(int i = 1; i < arg.length - 1; i++) {
int current = Math.max(Math.abs(maxForward[i] - minReverse[i + 1]), Math.abs(minForward[i] - maxReverse[i + 1]));
result = Math.max(result, current);
}
return result;
}

public static int[] helper(int[] arg, boolean isMax, boolean isForward) {

int[] result = new int[arg.length];
int[] current = new int[arg.length];

if(isMax && isForward) {
current = arg;
result = Math.max(0, current);
for(int i = 1; i < arg.length; i++) {
current[i] = Math.max(current[i - 1] + arg[i], arg[i]);
result[i] = Math.max(result[i - 1], current[i]);
}
} else if(!isMax && isForward) {
current = arg;
result = Math.min(0, current);
for(int i = 1; i < arg.length; i++) {
current[i] = Math.min(current[i - 1] + arg[i], arg[i]);
result[i] = Math.min(result[i - 1], current[i]);
}
} else if(isMax && !isForward) {
current[arg.length - 1] = arg[arg.length - 1];
result[arg.length - 1] = Math.max(0, current[arg.length - 1]);
for(int i = arg.length - 2; i > -1; i--) {
current[i] = Math.max(current[i + 1] + arg[i], arg[i]);
result[i] = Math.max(result[i + 1], current[i]);
}
} else {
current[arg.length - 1] = arg[arg.length - 1];
result[arg.length - 1] = Math.min(0, current[arg.length - 1]);
for(int i = arg.length - 2; i > -1; i--) {
current[i] = Math.min(current[i + 1] + arg[i], arg[i]);
result[i] = Math.min(result[i + 1], current[i]);
}
}
return result;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//O(N) time, O(N) space. Works for the [4,-1,7] case giving a result of 8 and for the case //mentioned in the post giving a result of 16.

public class MaxDiffSvc
{

public static int findMaxDiff(int[] arr)throws NullPointerException
{
if(arr==null)
{
throw new NullPointerException();
}
int maxDiff=Integer.MIN_VALUE();
int[][] cache=new int[arr.length];
cache=arr;//Max sum subarray seen so far
cache=arr;//Min sum subarray seen so far
cache=arr;//Cumulative sum seen so far
int minCumSum=0;//Index of minimum cumulative sum seen so far.
int maxCumSum=0;//Index of Maximum cumulative sum seen so far.

for(int i=1;i<arr.length;i++)
{
cache[i]=cache[i-1]+arr[i];
int c=cache[i];
int currMax=c-cache[minCumSum];//Maximum sum subarray with the element at i.
int currMin=c-cache[maxCumSum];//Minimum sum subarray with the element at i
//Take the current maximum and subtract the minimum sum subarray upto the index containing the minimum cumulative sum(update maxDiff if needed)
maxDiff=Math.max(maxDiff,Math.abs(currMax-cache[minCumSum]));
//Take the current minimum and subtract the maximum sum subarray upto the index containing the maximum cumulative sum(update maxDiff if needd)
maxDiff=Math.max(maxDiff,Math.abs(cache[maxCumSum]-currMin));

//Update the maximum and minimum sum subarray known to this point
cache[i]=Math.max(cache[i-1],currMax);
cache[i]=Math.min(cache[i-1],currMin);

//Update the maximum and minimum cumulative sums known to this point
minCumSum=c<cache[minCumSum]?i:minCumSum;
maxCumSum=c>cache[maxCumSum]?i:maxCumSum;

}
return maxDiff;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is DP problem to find minimum sub array and maximum sub array in the given array.

I think the solution for this array [2,-1,-2,1,-4,2,8] is simply finding minimum sub array and maximum sub array in the given array.

Maximum sub array and minimum sub array can be calculated in single sweep by below formula:

#global variable: maxValue & minValue (whenever min or max value if found update this.)

imaxSum= max (ithSum, ithvalue) & iminSum = min(ithSum, ithValue)

I cannot think of any use case where in max sub sequence array will overlap min sub sequence array.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The algorithm is so simple. Calculate the sum and find the split point where both ends has the biggest difference.

``````int maxDiff(int[] nums) {

int total = 0;
for (int i = 0;i < nums.length;i++) {
total += nums[i];
}

int bestDiff = 0, subTotal = 0;
for (int i = 0;i < nums.length;i++) {
subTotal += nums[i];

// total = sub + remain
int diff = Math.abs(subTotal - total) + Math.abs(total - subTotal - total);
if (diff > bestDiff) {
bestDiff = diff;
}
}

return bestDiff;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int maxSubArrayDifference(int[] arr) {
if (arr == null || arr.length < 2) return 0;

int[] minSumAtIdx = minSubArray(arr, false);
int[] minSumReverseAtIdx = minSubArray(arr, true);
int[] maxSumAtIdx = maxSubArray(arr, false);
int[] maxSumReverseAtIdx = maxSubArray(arr, true);

int diff = 0;
for (int i = 0; i < arr.length - 1; i++) {
int diff1 = Math.abs(maxSumAtIdx[i] - minSumReverseAtIdx[i + 1]);
diff = Math.max(diff, diff1);

int diff2 = Math.abs(maxSumReverseAtIdx[i + 1] - minSumAtIdx[i]);
diff = Math.max(diff, diff2);
}

return diff;
}

public static int[] minSubArray(int[] arr, boolean reverse) {
if (arr == null || arr.length == 0) return null;

int n = arr.length;
int[] minAtIdx = new int[n];

if (reverse) {
int minSoFar = arr[n - 1];
int min = arr[n - 1];
minAtIdx[n - 1] = arr[n - 1];

for (int i = n - 2; i >= 0; i--) {
minSoFar = Math.min(arr[i], arr[i] + minSoFar);
min = Math.min(min, minSoFar);
minAtIdx[i] = min;
}
} else {
int minSoFar = arr;
int min = arr;
minAtIdx = arr;

for (int i = 1; i < n; i++) {
minSoFar = Math.min(arr[i], arr[i] + minSoFar);
min = Math.min(min, minSoFar);
minAtIdx[i] = min;
}
}

return minAtIdx;
}

public static int[] maxSubArray(int[] arr, boolean reverse) {
if (arr == null || arr.length == 0) return null;

int n = arr.length;
int[] maxAtIdx = new int[n];

if (reverse) {
int maxSoFar = arr[n - 1];
int max = arr[n - 1];
maxAtIdx[n - 1] = arr[n - 1];

for (int i = n - 2; i >= 0; i--) {
maxSoFar = Math.max(arr[i], arr[i] + maxSoFar);
max = Math.max(max, maxSoFar);
maxAtIdx[i] = maxSoFar;
}
} else {
int maxSoFar = arr;
int max = arr;
maxAtIdx = arr;

for (int i = 1; i < n; i++) {
maxSoFar = Math.max(arr[i], arr[i] + maxSoFar);
max = Math.max(max, maxSoFar);
maxAtIdx[i] = maxSoFar;
}
}

return maxAtIdx;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

void findDisjointSubArraysWithMaxDiff() {
vector<int> input = {2, -1, -2, 1, -4, 2, 8};

unsigned size = (unsigned)input.size();

// Left to right find min/max subarrays ending at each index.
vector<MinMax> leftMinValues(size), leftMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> leftMinValuesUpto(size), leftMaxValuesUpto(size);

int minSoFar = 1;
int maxSoFar = -1;
leftMinValuesUpto = {INT_MAX, 0, 0};
leftMinValuesUpto = {INT_MIN, 0, 0};
for(int i=0; i< size; ++i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
leftMinValues[i] = {input[i], i, i};
} else {
leftMinValues[i] = {input[i]+minSoFar, leftMinValues[i-1].start, i};
}
minSoFar = leftMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
leftMaxValues[i] = {input[i], i, i};
} else {
leftMaxValues[i] = {input[i]+maxSoFar, leftMaxValues[i-1].start, i};
}
maxSoFar = leftMaxValues[i].value;

if (i == 0) {
leftMinValuesUpto = leftMinValues;
leftMaxValuesUpto = leftMaxValues;
} else {
leftMinValuesUpto[i] = leftMinValues[i].value < leftMinValuesUpto[i-1].value ? leftMinValues[i] : leftMinValuesUpto[i-1];
leftMaxValuesUpto[i] = leftMaxValues[i].value > leftMaxValuesUpto[i-1].value ? leftMaxValues[i] : leftMaxValuesUpto[i-1];
}
}

// RIGHT VALUES
// Left to right find min/max subarrays ending at each index.
vector<MinMax> rightMinValues(size), rightMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> rightMinValuesUpto(size), rightMaxValuesUpto(size);

minSoFar = 1;
maxSoFar = -1;
rightMinValuesUpto = {INT_MAX, (int)(size-1), (int)(size-1)};
rightMinValuesUpto = {INT_MIN, (int)(size-1), (int)(size-1)};
for(int i=size-1; i >=0; --i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
rightMinValues[i] = {input[i], i, i};
} else {
rightMinValues[i] = {input[i]+minSoFar, i, rightMinValues[i+1].end};
}
minSoFar = rightMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
rightMaxValues[i] = {input[i], i, i};
} else {
rightMaxValues[i] = {input[i]+maxSoFar, i, rightMaxValues[i+1].end};
}
maxSoFar = rightMaxValues[i].value;

if (i == 0) {
rightMinValuesUpto = rightMinValues;
rightMaxValuesUpto = rightMaxValues;
} else {
rightMinValuesUpto[i] = rightMinValues[i].value < rightMinValuesUpto[i-1].value ? rightMinValues[i] : rightMinValuesUpto[i-1];
rightMaxValuesUpto[i] = rightMaxValues[i].value > rightMaxValuesUpto[i-1].value ? rightMaxValues[i] : rightMaxValuesUpto[i-1];
}
//printf("\n MIN value: %d start: %d end: %d", rightMinValuesUpto[i].value, rightMinValuesUpto[i].start, rightMinValuesUpto[i].end);
//printf("\n MAX value: %d start: %d end: %d", rightMaxValuesUpto[i].value, rightMaxValuesUpto[i].start, rightMaxValuesUpto[i].end);
}

int range = INT_MIN;
MinMax one, two;
int splitAt;
for(int i=0; i<size-1; ++i) {
int range1 = rightMaxValuesUpto[i+1].value - leftMinValuesUpto[i].value;
int range2 = leftMaxValuesUpto[i].value - rightMinValuesUpto[i+1].value;
if (range1 > range2) {
if (range1 > range) {
range = range1;
one = leftMinValuesUpto[i];
two = rightMaxValuesUpto[i+1];
splitAt = i;
}
} else {
if (range2 > range) {
range = range2;
one = leftMaxValuesUpto[i];
two = rightMinValuesUpto[i+1];
splitAt = i;
}
}
}

printf("\n First SubArray: value: %d indexRange [%d: %d] \n Second SubArray: value: %d indexRange [%d: %d] \n splitAt: %d", one.value, one.start, one.end, two.value, two.start, two.end, splitAt);

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

``````void findDisjointSubArraysWithMaxDiff() {

vector<int> input = {2, -1, -2, 1, -4, 2, 8};

unsigned size = (unsigned)input.size();

// Left to right find min/max subarrays ending at each index.
vector<MinMax> leftMinValues(size), leftMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> leftMinValuesUpto(size), leftMaxValuesUpto(size);

int minSoFar = 1;
int maxSoFar = -1;
leftMinValuesUpto = {INT_MAX, 0, 0};
leftMinValuesUpto = {INT_MIN, 0, 0};
for(int i=0; i< size; ++i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
leftMinValues[i] = {input[i], i, i};
} else {
leftMinValues[i] = {input[i]+minSoFar, leftMinValues[i-1].start, i};
}
minSoFar = leftMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
leftMaxValues[i] = {input[i], i, i};
} else {
leftMaxValues[i] = {input[i]+maxSoFar, leftMaxValues[i-1].start, i};
}
maxSoFar = leftMaxValues[i].value;

if (i == 0) {
leftMinValuesUpto = leftMinValues;
leftMaxValuesUpto = leftMaxValues;
} else {
leftMinValuesUpto[i] = leftMinValues[i].value < leftMinValuesUpto[i-1].value ? leftMinValues[i] : leftMinValuesUpto[i-1];
leftMaxValuesUpto[i] = leftMaxValues[i].value > leftMaxValuesUpto[i-1].value ? leftMaxValues[i] : leftMaxValuesUpto[i-1];
}
}

// RIGHT VALUES
// Left to right find min/max subarrays ending at each index.
vector<MinMax> rightMinValues(size), rightMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> rightMinValuesUpto(size), rightMaxValuesUpto(size);

minSoFar = 1;
maxSoFar = -1;
rightMinValuesUpto = {INT_MAX, (int)(size-1), (int)(size-1)};
rightMinValuesUpto = {INT_MIN, (int)(size-1), (int)(size-1)};
for(int i=size-1; i >=0; --i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
rightMinValues[i] = {input[i], i, i};
} else {
rightMinValues[i] = {input[i]+minSoFar, i, rightMinValues[i+1].end};
}
minSoFar = rightMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
rightMaxValues[i] = {input[i], i, i};
} else {
rightMaxValues[i] = {input[i]+maxSoFar, i, rightMaxValues[i+1].end};
}
maxSoFar = rightMaxValues[i].value;

if (i == 0) {
rightMinValuesUpto = rightMinValues;
rightMaxValuesUpto = rightMaxValues;
} else {
rightMinValuesUpto[i] = rightMinValues[i].value < rightMinValuesUpto[i-1].value ? rightMinValues[i] : rightMinValuesUpto[i-1];
rightMaxValuesUpto[i] = rightMaxValues[i].value > rightMaxValuesUpto[i-1].value ? rightMaxValues[i] : rightMaxValuesUpto[i-1];
}
//printf("\n MIN value: %d start: %d end: %d", rightMinValuesUpto[i].value, rightMinValuesUpto[i].start, rightMinValuesUpto[i].end);
//printf("\n MAX value: %d start: %d end: %d", rightMaxValuesUpto[i].value, rightMaxValuesUpto[i].start, rightMaxValuesUpto[i].end);
}

int range = INT_MIN;
MinMax one, two;
int splitAt;
for(int i=0; i<size-1; ++i) {
int range1 = rightMaxValuesUpto[i+1].value - leftMinValuesUpto[i].value;
int range2 = leftMaxValuesUpto[i].value - rightMinValuesUpto[i+1].value;
if (range1 > range2) {
if (range1 > range) {
range = range1;
one = leftMinValuesUpto[i];
two = rightMaxValuesUpto[i+1];
splitAt = i;
}
} else {
if (range2 > range) {
range = range2;
one = leftMaxValuesUpto[i];
two = rightMinValuesUpto[i+1];
splitAt = i;
}
}
}

printf("\n  First SubArray: value: %d  indexRange [%d: %d] \n Second SubArray: value: %d  indexRange [%d: %d] \n   splitAt: %d", one.value, one.start, one.end, two.value, two.start, two.end, splitAt);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

``````void findDisjointSubArraysWithMaxDiff() {

vector<int> input = {2, -1, -2, 1, -4, 2, 8};

unsigned size = (unsigned)input.size();

// Left to right find min/max subarrays ending at each index.
vector<MinMax> leftMinValues(size), leftMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> leftMinValuesUpto(size), leftMaxValuesUpto(size);

int minSoFar = 1;
int maxSoFar = -1;
leftMinValuesUpto = {INT_MAX, 0, 0};
leftMinValuesUpto = {INT_MIN, 0, 0};
for(int i=0; i< size; ++i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
leftMinValues[i] = {input[i], i, i};
} else {
leftMinValues[i] = {input[i]+minSoFar, leftMinValues[i-1].start, i};
}
minSoFar = leftMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
leftMaxValues[i] = {input[i], i, i};
} else {
leftMaxValues[i] = {input[i]+maxSoFar, leftMaxValues[i-1].start, i};
}
maxSoFar = leftMaxValues[i].value;

if (i == 0) {
leftMinValuesUpto = leftMinValues;
leftMaxValuesUpto = leftMaxValues;
} else {
leftMinValuesUpto[i] = leftMinValues[i].value < leftMinValuesUpto[i-1].value ? leftMinValues[i] : leftMinValuesUpto[i-1];
leftMaxValuesUpto[i] = leftMaxValues[i].value > leftMaxValuesUpto[i-1].value ? leftMaxValues[i] : leftMaxValuesUpto[i-1];
}
}

// RIGHT VALUES
// Left to right find min/max subarrays ending at each index.
vector<MinMax> rightMinValues(size), rightMaxValues(size);

// min/max values from 0 to to upto current index (avove are ending at current index)
vector<MinMax> rightMinValuesUpto(size), rightMaxValuesUpto(size);

minSoFar = 1;
maxSoFar = -1;
rightMinValuesUpto = {INT_MAX, (int)(size-1), (int)(size-1)};
rightMinValuesUpto = {INT_MIN, (int)(size-1), (int)(size-1)};
for(int i=size-1; i >=0; --i) {
//cout<<"\n\n i: %d ";
if(input[i] < input[i]+minSoFar) {
rightMinValues[i] = {input[i], i, i};
} else {
rightMinValues[i] = {input[i]+minSoFar, i, rightMinValues[i+1].end};
}
minSoFar = rightMinValues[i].value;

if(input[i] > maxSoFar+input[i]) {
rightMaxValues[i] = {input[i], i, i};
} else {
rightMaxValues[i] = {input[i]+maxSoFar, i, rightMaxValues[i+1].end};
}
maxSoFar = rightMaxValues[i].value;

if (i == 0) {
rightMinValuesUpto = rightMinValues;
rightMaxValuesUpto = rightMaxValues;
} else {
rightMinValuesUpto[i] = rightMinValues[i].value < rightMinValuesUpto[i-1].value ? rightMinValues[i] : rightMinValuesUpto[i-1];
rightMaxValuesUpto[i] = rightMaxValues[i].value > rightMaxValuesUpto[i-1].value ? rightMaxValues[i] : rightMaxValuesUpto[i-1];
}
//printf("\n MIN value: %d start: %d end: %d", rightMinValuesUpto[i].value, rightMinValuesUpto[i].start, rightMinValuesUpto[i].end);
//printf("\n MAX value: %d start: %d end: %d", rightMaxValuesUpto[i].value, rightMaxValuesUpto[i].start, rightMaxValuesUpto[i].end);
}

int range = INT_MIN;
MinMax one, two;
int splitAt;
for(int i=0; i<size-1; ++i) {
int range1 = rightMaxValuesUpto[i+1].value - leftMinValuesUpto[i].value;
int range2 = leftMaxValuesUpto[i].value - rightMinValuesUpto[i+1].value;
if (range1 > range2) {
if (range1 > range) {
range = range1;
one = leftMinValuesUpto[i];
two = rightMaxValuesUpto[i+1];
splitAt = i;
}
} else {
if (range2 > range) {
range = range2;
one = leftMaxValuesUpto[i];
two = rightMinValuesUpto[i+1];
splitAt = i;
}
}
}

printf("\n  First SubArray: value: %d  indexRange [%d: %d] \n Second SubArray: value: %d  indexRange [%d: %d] \n   splitAt: %d", one.value, one.start, one.end, two.value, two.start, two.end, splitAt);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. We use Kadane's algorithm, which will compute sub array with max sum, at the same tiem we also compute min sub array. => O(n)
2. We use above to compute min/max sub-arrays from right to left. => O(n)
3. Above arrays contain min/max values ending at current index, now we parse them again, to find out min/max value upto the current index (doesn't have to end the current index) => O(n), this could be probably mixed with above step, seperatign it for clarity.
4. then we traverse again and see compare min/max for left/right to max range for each split point.
5. Along with min/max values we also save indices.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's what I came up with in Javascript using tabulation. The time complexity should be O(4n) which simplifies to O(n).

It ends up doing 4 loops (hence the 4n), and everything else inside and outside the loops is static (accessing/assigning elements in an array and comparing 2 numbers).

``````function maxDiffContiguousArrs2(arr) {

function helper(cb1, cb2) {
let l2rTab = new Array(arr.length - 1);
let r2lTab = new Array(arr.length - 1);

let tabLen = r2lTab.length;

l2rTab = arr;
r2lTab[tabLen - 1] = arr[arr.length - 1];

for (let i = 1; i < tabLen; i++) {
l2rTab[i] = cb1((arr[i] + l2rTab[i - 1]), arr[i])
r2lTab[tabLen - i - 1] = cb2((arr[arr.length - 1 - i] + r2lTab[tabLen - i]), arr[arr.length - 1 - i]);
}

let maxDiff = -Infinity

for (let i = 0; i < tabLen; i++) {
maxDiff = Math.max(Math.abs(l2rTab[i] - r2lTab[i]), maxDiff)
}
return maxDiff
}
return Math.max(helper(Math.min, Math.max), helper(Math.max, Math.min))
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote
Comment hidden because of low score. Click to expand.
0

the sets must consist of consecutive integers.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Is the exhaustive algo O(2^n * n) where n is # of digits in original set? Thats because you could make 2^n different pairs of subsets, and for each pair, you do sums of O(n).

I wonder if you could sort the origianal set and then walk up the sorted list, splitting it at each of the N points (forming the two subsets) and computing the difference of each of these subsets at each step, looking for the max? If so, you could optimize the sum, as you are just adding one new value to the sum of the first and removing it from the sum of the second.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

onestopinterviewprep.blogspot.com/2014/03/namespace-arrayproblem-write-function.html

Comment hidden because of low score. Click to expand.
-2
of 2 vote

The easiest solution posted ever, I wonder why people solve it so hard, just compute the sum of all elements, go through the array, compute the sum of first part=>second part, and compare :

``````int findMaxDiff(vector<int>& array) {
int sum=0;
for(int i=0; i<array.size(); ++i) {
sum+=array[i];
}
int sum1=0;
int max_diff=INT_MIN;
for(int i=0; i<array.size(); ++i) {
sum1+=array[i];
int diff=fabs((sum-sum1)-sum1);
if(diff>max_diff) max_diff=diff;
}
return max_diff;
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

easiet solution ever, wonder why people have written lines of code for this question:

``````int findMaxDiff(vector<int>& array) {
int sum=0;
for(int i=0; i<array.size(); ++i) {
sum+=array[i];
}
int sum1=0;
int max_diff=INT_MIN;
for(int i=0; i<array.size(); ++i) {
sum1+=array[i];
int diff=fabs((sum-sum1)-sum1);
if(diff>max_diff) max_diff=diff;
}
return max_diff;
}``````

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Proof of the assertion that they will not overlap is missing from this post...

Example:

[-1 0 1]

One subarray with minimum sum is [-1 0] and one with maximum sum is [0 1], and yet they overlap.

Note: You talked about finding "a" subset and do not give a method to choose [-1] over [-1 0].

Comment hidden because of low score. Click to expand.
0

[4, -1, 7]

max - [4, -1, 7] and min [-1]. It completely overlaps.

Comment hidden because of low score. Click to expand.
0

@Anonymous:
First off, a decent algorithm would never include 0 in the subsets if 0 is a boundary of interval, so the minimum sum and maximum sum subsets would be {-1} and {1} respectively and not {-1,0} and {0, 1}.

Secondly. the minimum sum subarray and maximum sum subarray can't overlap. they can however contain in each other completely.
Suppose that they overlap: split the sum of numbers into three parts: N + O + M
Where N is the sum of the minimum subset excluding the overlapping part.
O is the sum of the overlapping part
S is the sum of the maximum subset excluding the overlapping part

For N+O to be minimum O has to be -ve
M + O to be maximum O has to be +ve, a contradiction.

Comment hidden because of low score. Click to expand.
0

@Dumbo: Huh? What is the definition of "decent"? Even the wiki page on max-sum subarray problem has C++ code which will return [0, 1] and [-1, 0]. Check it out. (the code to give the exact subarray is commented).

Didn't read the rest of your post, but [4, -1, 7] is good enough to smash googlybhai's assertions (noted elsewhere in this thread).

Comment hidden because of low score. Click to expand.
0

@LAP what is the correct answer for [4, -1, 7]?

Is it (7) - (-1) = 8 or (4, -1, 7) - (empty set) = 10?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.