Microsoft Interview Question
Software Engineer / Developers Financial Software DevelopersYou can do it in 0(n), something like this:
void largestSum(int *numbers, int size, int **start, int **end)
{
if (!numbers || size < 0)
return;
int maxSum = 0;
int *maxStart = NULL;
int *maxEnd = NULL;
int *currStart = numbers;
int *currEnd = currStart;
int currSum = 0;
for (int index = 0; index < size; ++index)
{
currSum += *(numbers+index);
if (currSum < 0)
{
currStart = numbers+index+1;
currEnd = currStart;
currSum = 0;
}
else
{
if (currSum >= maxSum)
{
maxSum = currSum;
maxStart = currStart;
maxEnd = currEnd;
}
currEnd++;
}
}
*start = maxStart;
*end = maxEnd;
}
Assume the integers are in an array called intArray. The following code will do this
int beginIndex = 0;
int endIndex = 0;
int curValue = intArr[0];
long maxValue = curValue;
int maxBeginIndex = 0;
int maxEndIndex = 0;
for (int i = 1; i < number; i++)
{
curValue += intArr[i];
if (curValue > maxValue)
{
maxValue = curValue;
endIndex = i;
maxBeginIndex = beginIndex;
maxEndIndex = endIndex;
}
if (curValue < 0)
{
beginIndex = i+1;
endIndex = i+1;
curValue = 0;
}
}
The maxsubstring value is maxvalue and it is for numbers between maxBeginIndex and maxEndIndex.
No it won't.
First adding the next element of intArr to curValue and later checking whether curValue is greater than 0 does not work if curValue was less than 0 before the addition. So how can it be less than 0 before the addition? Answer; if the first element is negative. Try the sequence {-4,8}. The code gives {-4,8}, but the answer should have been {8}.
Try to make it O(n) running time and O(1) lookup initially.
There should exist at least one maximum value in this multiset. The max value can be reduced only when added with a smaller summond. It can be increased only when aded with a bigger summond. However, you need a continuous sequence. Therefore, adjust the seqStart index to contain the index prior to the smaller summond.
Vars:
unsigned seqStart=0;
Ex.1
6,-8, 3, -2, 4
Max=6
Ex.2
-8, 3, -2, 4
seqStart=0
hashtable=(0,-8),(1,3)
seqStart=1
hashtable=(1,3),(2,-2),(3,4)
This solution is O(1) lookup because of the hashtable. O(n) because you access each element of the array once.
One can consider two cases:
1. array is a mix of postive (possibly 0) and negative numbers
In this case, consider zero and the negative numbers as tokens and break the array around them. The sequence will be the subarray with the largest sum. This can be done in one pass.
2. array contains negative numbers only.
Pick the smallest number.
So without too much trouble, two passes solves the problem. I am sure there's a way to make one pass for both cases :-)
I think the alg worked for that particular multiset.
Let's examine this problem differently...
Example:
0 1 2 3 4 5 6 7 8 9
-2 4 6 -1 4 -9 2 -5 -3 9
Create hashtable.
numTable
You know that greater sums have greater avgs(7/3 > 5/3), so create a running avg. Take 0,pos nums always because they help maximize the sum.
avg=1
avg=2
avg=1 since the -1 produces a smaller avg, skip it and start another seq. Restore old avg to 2.
For -3,9:
avg=3;
resultant table:
(0,-2),(1,4),(2,6)
(8,-3),(9,9)
Calculate the greater sum from these and choose the sequence.
I'm not absolutely convinced this works. I would test it out thoroughly before stamping it.
This approach works...
ex: { 1, 3,-4, 5 -2, -1, 3 , 3, -1}
Iteration:1
Merge all continous +ves, and continous -ves
O(n) time
4, -4, 5, -3, 6,-1.
Iteration2:
You will have alternate +, -s now!!!!
From the first +ve, merge each triplet( 4, -4, 5), if -ve is less than both +ves. Continue from the point of merge!
O(n) time.
4,-4,8,-1.
Answer: 8
the current sequence is 5, -2,-1,3,3 which sum up to 8. so, we don't lose the sequence.
but i did not understand how it is 0(n) for 2nd step if we are checking each triplet
we have to store the sum in one place i guess and overwrite it if we get a greater sum
that is o(1) memory.
also for calculating the sum. what we can do is if we have the pointer at n
we must deduct the value of n-2 from that, and then add n+1 to it, but still it won't be O(n), because u have to compare with 2 elements on each side every time
assuming we're given the length of the array, i think this works although it has a run time of O(n^2):
int arr[] = {-6, 1, -3, 6, -8, 9, 0, 10, -5, 3};
int len; //assuming we're given the length of the array
int maxSum = 0;
int sum = 0;
int first=-1;
int last=-1;
int i, j, k;
for (i = 0; i < len; i++)
{
for (int j = i; j < len; j++)
{
for (k = i; k <= j; k++)
{
sum += arr[k];
}
if (i == 0 && j == 0)
{
maxSum = sum;
}
else if (sum > maxSum)
{
maxSum = sum;
first = i;
last = j;
}
sum = 0;
}
}
This is known as Bentley Algorithm. Bentley introduced this problem in his book called Programming Pearls. It's a great book. Highly recommended! If you look at the beginning of this page, SN gave us the correct algorithm. You can do it in O (N) time and constant memory. SN algorithm doesn't work if the array are all negative numbers. One way to fix this is first, find the largest number in the array. If the number is negative, that number would be the largest subarray. If not, use the algorithm that SN gave.
This is called the maximum sum subsequence problem. Here we need to note that if we come across a negative sum we might as well not start our sequence from there. A special case would be when all the input elements are negative. We can use prefix sums to solve this problem in O(n) time. There is also a O(n log n) solution available.
int a[] = {6,-8, 3, -2, 4};
maxsum = 0;
sum = 0;
for(i = 0; i < n; i++){
sum += a[i];
if (maxsum < sum){
maxsum = sum;
}
else{
if(sum < 0){
sum = 0;
}
}
}
This can be solved by Divided and conquer Approach.
Lets say A is the array. P and Q are indeices of the two ends. If there are n numbers, P = 1 and Q = n.
So the pseudocode will be as below;
MAXSUM(A,P,Q)
if P=Q-1 then
return the element
end if
r = P+Q /2
max1 <- MAXSUM(A,P,r)
max2 <- MAXSUM(A,r+1,Q)
maxPartition = 0;
for i = 1 to n
L <- summation of i elements from r towards P
M <- summation of i elements from r towards Q
if ((L+M) > maxPartition) then
maxPartition = L+M
end if
end for
return max(max1, max2, maxPartition)
Complexity: O(nlogn)
Dynamic programming is a rite way,
int findMaxSub(int a[], int n, int& p1, int& p2){
if(n==0){
p2 = -1;
p1 = -1; // used to check if error
return 0;
}
int max = a[0];
int p_sum = a[0];
int p_start = 0;
int p_end = 0;
p1 = 0;
p2 = 0;
for(int i = 1; i<n; i++){
if(p_sum < 0){
// partial sum can be discarded
p_start = i;
p_end = i;
p_sum = a[i];
}
else{
// keep counting the previous partial sum
p_sum +=a[i];
p_end = i;
}
if(p_sum > max){
p1 = p_start;
p2 = p_end;
max = p_sum;
}
}
return max;
}
Everybody seems to assume that a negative sum is an error condition, but what if I still want to find the continuous sequence with the largest sum even if it's a negative number. Here is an example: {-5, -1, -3, -6, -9}
In this case, shouldn't {-1} be the answer? Am I missing something here? Thanks,
#define MAX 5
#include<stdio.h>
int main(){
int a[MAX]={6,10,-3,-2,4};
int gi=0,gj=0,i=0,j=0,k=0,l=0,sum=0,gsum=0;
for(i=0;i<MAX;i++) {
for(j=0;j>=i,j<MAX;j++){
k=i;
l=j;
sum=0;
for(;k<=l;k++){
sum +=a[k];
}
if(gsum<sum){
gsum=sum;
gi=i;
gj=j;
}
}
}
l=gi;
k=gj;
printf("{");
for(;l<=k;l++){
printf("%d",a[l]);
printf("\t");
}
printf("}");
}
i knew that the solution will fail if all numbers r negative but its not a big deal man
just find out the greatest number in the array and put
gsum=greatest;
add this to main
gsum=a[0];
for(int i=0;i<MAX;i++){
if(a[i]>gsum)
gsum=a[i];
}
i think u must have got it till now
anyway thanx for looking in the code
//sorry their was a smaall mistake in the comparision in second for loop so number of cases missed check it out now
its working perfectly
#define MAX 5
#include<stdio.h>
int main(){
int a[MAX]={-6,-10,-3,-2,-4};
int gi=0,gj=0,i=0,j=0,k=0,l=0,sum=0,gsum;
gsum=a[0];
for( k=0;k<MAX;k++){
if(a[k]>gsum)
gsum=a[k];
}
//printf("%d",gsum);
for(i=0;i<MAX;i++) {
for(j=0;j<MAX;j++){
if(j>=i){
k=i;
l=j;
sum=0;
for(;k<=l;k++){
sum +=a[k];
}
if(gsum<=sum){
gsum=sum;
gi=i;
gj=j;
}
}
}
}
l=gi;
k=gj;
printf("%d%d",l,k);
printf("{");
for(;l<=k;l++){
printf("%d",a[l]);
printf("\t");
}
printf("}");
}
Works for even all negative numbers in the array
static void FindMaxSubArray(int[] array)
{
if (array == null)
{
throw new ArgumentNullException("array");
}
if (array.Length == 0)
{
return;
}
int maxStart = -1;
int maxEnd = -1;
int start = 0;
int end = 0 ;
long currentSum = 0;
long maxSum = long.MinValue;
while(end < array.Length)
{
currentSum = currentSum + array[end];
if (currentSum > maxSum)
{
maxStart = start;
maxEnd = end;
maxSum = currentSum;
}
if (currentSum < 0)
{
start = end + 1;
currentSum = 0;
}
end++;
}
PrintMaxSubArray(array, maxStart, maxEnd);
}
It covers most of the cases.
void findMaxCountSeq(int *array, int size)
{
using namespace std;
map <int, int> charMap;
int sum = 0;
for(int i = 0; i < size; i++)
{
if(array[i] < 0)
{
if((sum + array[i]) > 0)
{
sum += array[i];
charMap[i] = sum;
}
else
{
charMap[i] = -1;
sum = 0;
}
}
else
{
sum += array[i];
charMap[i] = sum;
}
}
printf("Array :: ");
for(i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
printf(" \n");
int maxstartIndex = -1;
int maxendIndex = 0;
int maxvalue = 0;
int tempStartIndex = 0;
int tempendIndex = 0;
for(i = 0; i < size; i++)
{
tempStartIndex = i;
while(charMap[i] > 0 && i < size)
{
i++;
}
tempendIndex = i-1;
if(maxvalue < charMap[tempendIndex])
{
maxstartIndex = tempStartIndex;
maxendIndex = tempendIndex;
maxvalue = charMap[tempendIndex];
}
}
if( maxstartIndex == -1) // all are negative numbers
{
// get the maximum of the available numbers.
maxvalue = array[0];
maxstartIndex = 0;
maxendIndex = 0;
for(i = 0; i < size; i++)
{
if(maxvalue < array[i])
{
maxvalue = array[i];
maxstartIndex = i;
maxendIndex = i;
}
}
}
printf("Max Value: %d sIndex: %d eIndex: %d\n", maxvalue, maxstartIndex,maxendIndex);
}
This code will work for any array
void MaxSubArray(int a[], int n, int& begin, int& end)
{
if( a == NULL || n <= 0)
{
begin = end =-1;
return;
}
int tmpStart = 0;
int maxSum = a[0];
int curSum = a[0];
int tmpEnd = 0;
for(int i=1;i<n;i++)
{
curSum = curSum + a[i];
if( curSum > maxSum)
{
maxSum = curSum;
tmpEnd = i;
}
else if( curSum < 0)
{
tmpStart = i+1;
curSum = 0;
}
}
if( tmpStart > tmpEnd)
tmpStart = tmpEnd;
begin = tmpStart;
end = tmpEnd;
}
max = A[0];
sum = 0;
for(i = 0 to n)
{
sum += A[i];
if(sum > max)
max = sum;
if(sum<0)
sum = 0;
}
return max;
Can someone give a test case for which the above code will fail ?
This should do the trick for both positive and negative...:)
public void maxSubsequence(int[] arrayToFindSum) {
maxSum = arrayToFindSum[0];
int thisSum = 0;
for (int i = 0, j = 0; j < arrayToFindSum.length; j++) {
thisSum += arrayToFindSum[j];
if (thisSum > maxSum) {
maxSum = thisSum;
startSeq = i;
endSeq = j;
}
if (thisSum < 0) {
i=j+1;
thisSum=0;
}
}
}
The return type is an array in the original question at the top and most of the solutions above are returning sum??. Here is what I have comeup with (Not efficient interms of Big-O but it works:
public static int[] FirstConsecutiveSequenceWithMaxSum(int[] inputArray)
{
//local variables
int _startIndex=0, _endIndex=0;
int _currentMax=0, _currentLoopMax=0, _newLoopSum=0;
int l = inputArray.Length; //input array size
int[] _returnArray;
//boundary case.
if (l == 0)
{
//throw exception or return blank array as per user requirements
//TODO
}
if (l == 1)
{
return inputArray;
}
for (int i = 0; i < l; i++)
{
if (inputArray[i] > 0)
{
for (int j = i; j < l; j++)
{
_newLoopSum += inputArray[j];
if (_newLoopSum > _currentMax)
{
_currentMax = _newLoopSum;
_startIndex = i;
_endIndex = j;
}
}
//reset current loop sum
_newLoopSum = 0;
}
}
int _returnArrayLength = _endIndex - _startIndex + 1;
_returnArray = new int[_returnArrayLength];
for (int i = 0; i < _returnArrayLength; i++)
{
_returnArray[i] = inputArray[_startIndex++];
}
return _returnArray;
}
void LargestSum(int a[], int size, int& start, int& end)
{
start = -1;
end = -1;
if(a == NULL || size <= 0)
return;
int sum = 0;
int maxsum = 0;
bool bStartFlag = false;
int newstart = 0;
for(int i = 0; i < size; i++)
{
sum += a[i];
if(sum > 0)
{
if(bStartFlag == false)
{
bStartFlag = true;
newstart = i;
}
}
else
{
sum = 0;
bStartFlag = false;
}
if(sum > maxsum)
{
end = i;
if(bStartFlag)
{
start = newstart;
}
}
}
}
maxSum = 0
for L = 1 to N
{
sum = 0
for R = L to N
{
sum = sum + X[R]
maxSum = max(maxSum, sum)
}
}
- Iterating inner loop calculating the sum of all the number and comparing it with maximum sum.
This will be O(n)
This isn't O(n) its O(n^2). The following, from Jon Bentleys 'Programming Pearls' is O(n)
float MaxSubSequence(float *v, int n)
{
float maxSoFar=v[0];
float maxEndingHere=v[0];
for (int i=1; i<n; ++i)
{
maxEndingHere = max( maxEndingHere+v[i],0.0f );
maxSoFar = max( maxSoFar, maxEndingHere );
}
return maxSoFar;
}
There could be two solutions:
1.) brute force add two zero's infront of the array.
{for(i=0;i<num-3;i++)
{for(j=i;j<num-2;j++)
{for(k=j;k<num;k++)
{
compare if the sum is of a[i]+a[j]+a[k] is greater than the largest else replace
}
}
}
complexity n^3
2.)if the integrity of the array is not important
do a quick sort
check the last number in array put it in max, then add it to the second last if it becomes less max is the rite answer else put the sum in max try adding the third last
max complexity nlog(n)+3 else nlog(n)+1
** in both the cases map the all elements location.
Reference: codeproject.com/KB/recipes/Max_Subssequence.aspx
class seqresult{
public int start;
public int end;
public int sum;
//constructor
public seqresult(){
start=-1;
end=-1;
sum=0;
}
//restart the sequence at the current position
public void restart(int index, int value){
start=index;
end=index;
sum=value;
}
//extend the sequence by adding the current position
public void extend(int value){
end++;
sum+=value;
}
public void print(){
System.out.println("sum= "+sum+"; start= "+start+"; end= "+end);
}
public void copy(seqresult s){
this.end=s.end;
this.start=s.start;
this.sum=s.sum;
}
}
public class largestsequence {
public static void main(String[] args){
int[] array={ -2, 11, -4, 13, -5, 2 };
findmaxconseq(array);
}
public static void findmaxconseq(int[] array){
seqresult current=new seqresult();
seqresult max=new seqresult();
max.restart(0, array[0]);
current.restart(0, array[0]);
for(int i=1;i<array.length;i++){
int sum=array[i]+current.sum;
if(array[i]>sum) current.restart(i, array[i]);
else{
current.extend(array[i]);
}
if(current.sum>max.sum){
max.copy(current);
}
}
max.print();
}
}
two solutions
O(n^2)
ThisSum=0;
MaxSum=0;
for (int i =0; i < n; i++)
{
ThisSum=0;
for (int j = 0; j < n; j++;)
{
ThisSum += Array[j];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
}
retunn MaxSum;
}
--------------------------
Another Very succint Solution from Programming pearls
MaxSumSoFar = 0;
MaxEndingAtThisIndex= 0;
for (int index =0; index < size; index ++)
MaxEndingAtThisIndex = Max(MaxEndingAtThisIndex + Array[j],0);
MaxSumSoFar = Max(MaxSumSoFar, MaxEndingAtThisIndex);
}
int Max(int a, int b)
{
return(a>b?a:b);
}
int maxsum(int a[], int length)
{
int b = 0;
int sum = INT_MIN;
int start_index = 0, end_index = 0;
int new_start_index = 0;
for(int i = 0; i < length; ++i)
{
if(b > 0)
{
b += a[i];
}
else
{
new_start_index = i;
b = a[i];
}
if(b > sum)
{
start_index = new_start_index;
end_index = i;
sum = b;
}
}
for(int i = start_index; i <= end_index; ++i)
{
printf("%d ", a[i]);
}
printf("\n");
return sum;
}
}
Here's a O(n) solution that's similar to some of those posted already, except I tried to address the following:
(1) When all numbers are negative, it should still work
(2) Return the list of numbers, rather than just the maximum itself
(3) Avoided using a separate array to do it the DP way
Algorithm is:
(1) Keep a running sum, call it curr
(2) Whenever it exceeds the current max, set max to it. Also set end to the current array index so we can reproduce the sequence from it
(3) If running sum is below 0, we will just reset it to 0 because there's no reason to add onto a negative running sum
static ArrayList<Integer> maxSequence(int[] arr) {
int max = arr[0];
int end = 0;
int curr = 0;
for(int i=0; i<arr.length; i++) {
curr += arr[i];
if(curr > max) {
max = curr;
end = i;
} else if(curr < 0) {
curr = 0;
}
}
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=end; max!=0; i--) {
result.add(0, arr[i]);
max-=arr[i];
}
return result;
}
This one works. A bit longer and requires an extra data structure. But a clean implementation:
public class Range
{
public int start, end, sum;
}
public static List<int> BiggestSumSet(List<int> numbers)
{
List<Range> ranges = new List<Range>();
Range r = new Range();
int i = 0;
while (i < numbers.Count)
{
r.start = i;
while (i < numbers.Count && numbers[i] >= 0)
{
r.sum += numbers[i];
r.end = i++;
}
ranges.Add(r);
r = new Range();
r.start = i;
while ( i < numbers.Count && numbers[i] < 0)
{
r.sum += numbers[i];
r.end = i++;
}
ranges.Add(r);
r = new Range();
r.start = i;
}
i = 0;
int maxIndex = i;
for (i = 1; i < ranges.Count; i++)
{
if (ranges[i].sum > ranges[maxIndex].sum)
maxIndex = i;
}
i = maxIndex+1;
int totalSum = ranges[maxIndex].sum;
while(i < ranges.Count)
{
totalSum += ranges[i].sum;
if (totalSum > ranges[maxIndex].sum)
{
ranges[maxIndex].end = ranges[i].end;
}
i++;
}
if (totalSum < ranges[maxIndex].sum)
{
totalSum = ranges[maxIndex].sum;
}
i = maxIndex-1;
while (i >= 0)
{
totalSum += ranges[i].sum;
if (totalSum > ranges[maxIndex].sum)
{
ranges[maxIndex].start = ranges[i].start;
}
i--;
}
return numbers.GetRange(ranges[maxIndex].start, ranges[maxIndex].end - ranges[maxIndex].start + 1);
}
int[] inputs = new int[] { 6, -8, 3, -2, 4 };
//int startIndex = 0;
int endingStartIndex;
int endIndex = inputs.Length -1;
int maxValue = int.MinValue;
int currValue;
for (int startIndex = 0; startIndex < inputs.Length; startIndex++)
{
currValue = inputs[startIndex];
for (int i = startIndex+1; i < inputs.Length; i++)
{
currValue += inputs[i];
if (currValue > maxValue)
{
maxValue = currValue;
endIndex = i;
endingStartIndex = startIndex;
}
}
}
6 > (3 -2 + 4)
- Dan June 16, 2005