Microsoft Interview Question
Country: United States
-9 -11 2 5 3 -12
sum=-9-11+2+5+3-12=-22
max neg sum=-22
-22+22=0
so acc to u
ans=0
while ans=10
Hey..nice one..looks like it works, but cant be sure unless ders a proof for it... can u prove it??
well, the idea is correct but it's not going to work that easy: Remember the numbers are written on a *circle*.
while Kadane's algo just computes a maximal contiguous subsequence. How'd handle when you subsequence wraps around ?
The solution to this is provided in stackoverflow question number 6047590.
max_start=0; max_end =0; maxv = 0; sum 0;
for i in range(arr):
sum+= arr[i];
if sum<0:
sum=0; max_start =i;
if maxv<sum:
maxv=sum; max_end = i;
#seocnd pass
for i in range(max_start):
sum+= arr[i];
if sum<0:
break;
if maxv<sum:
maxv=sum;max_end = i;
if I get it correctly, this algo can still miss some solutions:
Ie. consider {2, 5, -6, 3, 7}
after the first pass you'd have: max_start = 0, max_end = 4, maxv = 11. And the second pass is not executed since range(max_start) = 0. While the correct answer should be: 17.
To solve this problem, imagine that the array is triplied, I mean if we write 2, 5, -6, 3, 7 in the following way:
5, -6, 3, 7, 2, 5, -6, 3, 7, 2, 5, -6, 3. We can build an array with dimensions multiplied by 3 and It would O(3*n)=O(n).
The second and more efficient approach would be using modular numbers to transverse the array. The code could be the next:
int max=0; int tmp=0; int count=0;//We want to get at the maximum "length" numbers.
for(int i=0;i<length*3;i++)
{
tmp=tmp+a[i%length];
count++;
if((tmp<0)||(count>length))
{
tmp=0;count=0;
}else if(tmp>max){
max=tmp;
}
}
static int[] ReverseSubString(int[] Arr, int indx1, int indx2)
{
int Cnt = indx2 - indx1;
for(int i=indx1; i<= indx1+(int)(Cnt/2);i++)
{
int tmp = Arr[i];
Arr[i] = Arr[indx2 - (i - indx1)];
Arr[indx2 - (i - indx1)] = tmp;
}
return Arr;
}
public static int FindMax(int[] Arr, int Cnt)
{
int MaxSum = 0;
int TillSum = 0;
for (int i = 0; i <Cnt ; i++)
{
TillSum = (TillSum + Arr[i] > 0) ? TillSum + Arr[i] : 0;
MaxSum = (TillSum > MaxSum) ? TillSum : MaxSum;
}
return MaxSum;
}
public static int[] ReverseInCyle(int[] Arr, int Cnt)
{
int MidIndx = (int)Cnt / 2;
Arr = ReverseSubString(Arr, 0, MidIndx);
Arr = ReverseSubString(Arr, MidIndx + 1, Cnt - 1);
return Arr;
}
static void Main(string[] args)
{
int[] numbers = new int[10];
numbers[0] = 1;
numbers[1] = 14;
numbers[2] = 11;
numbers[3] = -2;
numbers[4] = 9;
numbers[5] = 4;
numbers[6] = -5;
int Cnt = 7;
int Max1 = FindMax(numbers, Cnt);
numbers = ReverseInCyle(numbers, Cnt);
int Max2 = FindMax(numbers, Cnt);
int Max = Max2 > Max1 ? Max2 : Max1;
Console.WriteLine(Max);
}
}
This will find the max in a circular way. The idea here is to first find max & then shift the array in circular way & again find the max. For e.g. {1,2,3,-4,5,6,-9} .. The first max will be
13. Then on circular shift, it will be {3,2,1,-9,6,5,-4}. Here the max will be 11. The max of both is 13. So answer is 13. The above code does the same. it's in c sharp. Let me know if it won't work under any cases?
[-3, 5, 6, -2, -2, 2, 2]
-------------------------------------------------------------------------------
-3,5,11,9,7,9,11 < Maximum sub sequence at a given point>
Now do a wrap around
8 , End,
let us examine from where the sequene starts it is from 5
Are they any negetive numbers in between?
yes -2,-2
After every negetive number start the maximum subsequence again with hope that it may find more positive during wrap around..............(we can also optimize a bit here )
Find the index of the smallest value and just skip it.
For example: { 2, 5,6, -15, 11, -10, 15}
The normal running sum wound be [ 11, -10, 15] = 16
The smallest index is 3 (-15).
if the index is at 3, increment it to 4.
The result is 29. { 11, -10, 15, 2, 5, 6 }
The main idea is to wrap around the max sum..
1.find the max sum n nos using kadane's algo
2.Use DP to remember Max sum's
3.wrap around the sum..i.e start from each no
4.if the 1st no is -ve remove the no from max sum
eg..
-3 5 6 -2 -2 2 2
1.find max sum for the sq->11
2.start including circula wise start from 5 and include -3 in the sum element include .store the sum in a DP.
3.when startng from a -ve no dont include it in sum.For the array starting in -2 dont include it
finally max of DP array will give u the sum
content of DP array 11 8 8 10 12 10 8
hope u got my approach its O(n) with extra space of n
Here is the solution I think can work to get O(n) but will add a space of N (without any optimization) of array which is definitely better than using a hashtable or any other expensive inbuilt construct I think.
For each index in array A starting from 0, keep track of maxSum value and currentSum values for an index using two separate arrays say Current[n] and Maximum [n]. For each index i in A, keep updating the value of Current[] and update Maximum[] if exceeing the previous maximumsum for valid/qualified indexes which have been visited(started) once and have not been touched again yet. After we finish two rounds of trversals on array (with wrap around) we should have an answer for the maximum value for a given index from array Maximum[] i.e;Maximum[maxValueIndex]. Complexity is O(2n) for traversal + O(n) to look for max value in Maximum Array = O(3n) == O(n).
One can cut down on the memory space requirement by counting the number of +s numbers as those are the only valid starting point.
Here is more optimized solution.
The space requirement can greatly optimized by condensing the initial array's + and -patches and using a new array which sould be in the format
+, -,+ -,.....
or
-, +, -, +,.....
and having the Maximum and Minimum array lengths only for the number of positive numbers as negative condensed sums don't qualify as desireable staring points in my opinion.
As an example for overall optimized solution
{-3, 5, 6, -2, -2, 2, 2} = {-3,11,-4,4} --> Condensed Array. --> doesn't need to be actually created.
MAXIMUM={8,12} --> only for + starting points being useful.
Value of Current[] after each starting index complete cyclic iteration.(only for + values in condensed array)
CURRENT={8,8} --> only for +ve staring points as mentioned above.
Finally after searching in MAXIMUM for maximum value, we find that maximum value is for the second positive patch in original array starting at index 5.
Maximum Space complexity for the condensed solution = N for an original pure alternating pattern of +,-,+, -....for any other original pattern say +++,--,...etc, extra space complexity is less than n so O(N).
Note we don't actualy need to store the condensed array as it can be computed during run time by adding the patches. Time complexity is O(N)
Another Example as mentioned above
{2, 5, -6, 3, 7}. == {7,-6,10} --> Condensed
CURRENT={11,11}
--> Current array values after each complete iteration for positive patch would be always same.
MAX={11,17} --> 17 maximum value for second postive patch.
Another example discussed above.
{ 2, 5,6, -15, 11, -10, 15}== {13,-15,11,-10,15}
MAXIMUM={14,29,28} --> 29 is the max value starting at second positive patch.
current={14,14,14}
A simple solution will be to
1) create an array of size twice that of original one
2) copy the original array to new array twice. For example if the initial array is 1 2 3, new array is 1 2 3 1 2 3.
3) Now solve it normally like we do for non circular ones. The only constraint is the start of the max sequence should be < n (size of original array) and its length should be < n
#include <iostream>
using namespace std;
int dp[1000];
int pos[1000];
int MaxSum(int* input, int num)
{
int* dupInput = (int*)malloc(2*num*sizeof(int));
for(int i = 0;i < num; i++)
{
dupInput[i] = input[i];
dupInput[i + num] = input[i];
}
dp[0] = dupInput[0];
pos[0] = 0;
for(int i = 1; i < 2*num; i++)
{
if(dp[i-1]>0)
{
dp[i] = dupInput[i] + dp[i-1];
pos[i] = pos[i-1];
}
else
{
dp[i] = dupInput[i];
pos[i] = i;
}
}
int max = -1000000;
for(int i = 0; i < 2*num; i++)
{
if(dp[i] > max && i - pos[i] < num)
max = dp[i];
}
return max;
}
int main()
{
int a[] = {8, -8, 9, -9, 10, -11, 12};
cout << MaxSum(a, 7) << endl;
char c;
cin >> c;
return 1;
}
#include <iostream>
using namespace std;
int dp[1000];
int pos[1000];
int MaxSum(int* input, int num)
{
int* dupInput = (int*)malloc(2*num*sizeof(int));
for(int i = 0;i < num; i++)
{
dupInput[i] = input[i];
dupInput[i + num] = input[i];
}
dp[0] = dupInput[0];
pos[0] = 0;
for(int i = 1; i < 2*num; i++)
{
if(dp[i-1]>0)
{
dp[i] = dupInput[i] + dp[i-1];
pos[i] = pos[i-1];
}
else
{
dp[i] = dupInput[i];
pos[i] = i;
}
}
int max = -1000000;
for(int i = 0; i < 2*num; i++)
{
if(dp[i] > max && i - pos[i] < num)
max = dp[i];
}
return max;
}
int main()
{
int a[] = {8, -8, 9, -9, 10, -11, 12};
cout << MaxSum(a, 7) << endl;
char c;
cin >> c;
return 1;
}
public class MaxCircularSubArraySum {
private static int findMaxSubArraySum(int a[]) {
int maxSum = Integer.MIN_VALUE, maxSumSoFar = 0;
int minSum = Integer.MIN_VALUE, minSumSoFar = 0;
int totSum = 0;
boolean zeroExists = false;
for (int i = 0; i < a.length; ++i) {
if (a[i] == 0) {
zeroExists = true;
}
totSum += a[i];
if (minSumSoFar < 0) {
minSumSoFar = 0;
}
minSumSoFar += -a[i];
if (minSum < minSumSoFar) {
minSum = minSumSoFar;
}
if (maxSumSoFar < 0) {
maxSumSoFar = 0;
}
maxSumSoFar += a[i];
if (maxSum < maxSumSoFar) {
maxSum = maxSumSoFar;
}
}
int ret = (maxSum < totSum + minSum) ? totSum + minSum : maxSum;
if (!zeroExists & ret == 0) {
ret = maxSum;
}
return ret;
}
public static void main(String[] args) {
System.out.println(findMaxSubArraySum(new int[] { 8, -8, 9, -9, 10,
-11, 12 }));
System.out.println(findMaxSubArraySum(new int[] { 1, 2, 3, 4, 5 }));
System.out
.println(findMaxSubArraySum(new int[] {0, -1, -2, -3, -4, -5 }));
}
}
void modifiedKadane (int elements [], int length )
{
int maxSum = -1;
int currentSum = 0;
int maxStartIndex = 0, maxEndIndex = 0, s = 0, i = 0;
/*
* Run algorithm for twice the length of the array to get the circular input effect.
*/
for (i = 0; i < 2 * length; ++i)
{
/*
* Check to see if the numbers of elements used to get maxSum is not greater than length.
*/
if (i - s == length)
{
currentSum = 0;
s = s + 1;
i = s;
}
/*
* Classic Kadane's algorithm.
*/
currentSum = currentSum + elements [i % length];
if (currentSum > maxSum)
{
maxSum = currentSum;
maxStartIndex = s;
maxEndIndex = i;
}
if (currentSum < 0)
{
currentSum = 0;
s = i + 1;
}
}
printf ("Sum = %d Start = %d End = %d\n", maxSum, maxStartIndex % length, maxEndIndex % length);
}
As people suggested above, use DP:
1. Matrix A where row denotes the starting position and column denotes the element no. upto which sum is calculated.
Eg. A[5,3] = Sum of elements starting from 5th element to the 3rd element (considering elements are in circle)
A[N,K] = A[N,K - 1] + A[K,K] ... If K > 0
A[N,0] = A[N, last] + A[0,0] ... because of rounding sum
Remember the max entry in array and thus we can tell the start and end of sequence:
if A[X,Y] is max then array starts from X and ends in Y.
As people suggested above, use DP:
1. Matrix A where row denotes the starting position and column denotes the element no. upto which sum is calculated.
Eg. A[5,3] = Sum of elements starting from 5th element to the 3rd element (considering elements are in circle)
A[N,K] = A[N,K - 1] + A[K,K] ... If K > 0
A[N,0] = A[N, last] + A[0,0] ... because of rounding sum
Remember the max entry in array and thus we can tell the start and end of sequence:
if A[X,Y] is max then array starts from X and ends in Y.
this is easy
int currentMax = 0;
int maxSoFar = 0;
for (int i = 0; i < array.size() * 2 - 1; i ++)
{
currentMax += array[i % array.size()];
if (currentMax > maxSoFar)
maxSofar = currentMax;
if (currentMax < 0)
{
if ( i >= array.size())
break;
currentMax = 0;
}
}
If we find the least element in the array and make that our start or head pointer.. then we start summing up from that location using the following logic:
S(n): where S(n) is the max sum of the array ending a i'th index.
S(n) = Max { element(n), element(n) + S(n-1) }
So, for the 1st example, the arrays look like:
element(): {8,-8,9,-9,10,-11,12}. Here in the first linear pass, we find the least value element (which in this case is -11). We start couting from -11. So for simplicity sake, let us imagine the element() as:
{-11,12, 8,-8,9,-9,10}
S() : {-11,12,20,12,21,12,22}. now do a linear traversal to find the max sum in S()
For the 2nd example, we have the following:
element(): {2, 5, -6, 3, 7}. Again finding the least element in this array and starting from there, we have elements() as {-6, 3, 7, 2, 5}
So, S(n): {-6,3,10,12,17}
hence, the max is 17
@Jester: Nice solution, but it requires altering the original array (or creating new array to have a sequence starting from minimum element).
Most elegant solutions don't modify the input data.
@Learner we are not modifying the original array. im just using an extra node* to refer to the pseudo-starting location of the list. so the only overhead i incur is initializing thus pointer to the address of the least element. after the summation is done, memory occupied by this pointer is freed.
so we're not modifying the original list or creating a new one.. just one new pointer
Well, how about this? .... Let the sum of all elements in the array be S. First, forget about the wrap-around case and find the max sum of the 1D array using the Kadane approach. Say its M. Next, modify the Kadane algo a bit to find the max negative sum. Say its -N. Now check if (S+N) > M. If yes, the answer is S+N, otherwise its M. I think this should work. However please let me know if you find any case for which this logic might fail.
- sam8dec February 23, 2012