sugandhapacific
BAN USERI 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)
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?
- sugandhapacific August 06, 2013My 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)