Microsoft Interview Question for Software Engineer / Developers Financial Software Developers






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

6 > (3 -2 + 4)

- Dan June 16, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

You 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;
}

- SomeSDE June 03, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Check Kadane's Algo for the solution

- solutionyoda January 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

WHAT I MEAN IS HOW LONG IS THE SEQUENCE..IS IT A SIZE 3 SEQUENCE (THATS WHY {3,-2,4}) OR WHAT? :CONFUSED:


PEACE.

- WHIZKID June 17, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guess I wasn't paying attention when I wrote this. The example should have given {6} as the answer.

- Gayle L McDowell June 20, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- SN October 16, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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}.

- T.Aho October 21, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can do check for each individual element once then each pair each triplet and so on, and compare the max values in each case
but this is a pretty long procedure any easier solutions please

- Sourav February 14, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jack February 14, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi jack i did not get it can u explain in a little more detail.
also, let's say we have 6, then -4, then + 5 , then we can not ignore the -4 also, because 6-4+5 =7 , which is > 6

- Sourav February 15, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 :-)

- Reda E. February 15, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jack February 15, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Jack,
Greater sums do not have greater avgs is not a general rule unless the sums have the same number of elements (counter example {5} and {5,4}). It's most efficient to keep a running sum than a running avg.

- Reda E. February 16, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ajay February 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ajay..
can u explain me the second step... how did u arrive at 4,-4,8,-1 from 4,-4,5,-3,6,-1. what do u mean by -ve is less than both +ves.

- kiran February 19, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Kiran, What Ajay meant was that the absolute value(|-3|) is less than 5 and 6. So only if thats the case then you add up the triplet.

Ajay that was a good trick to do it.

- Vikas February 20, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

But don't we loose the sequence in this approach? I mean..I understood it as we need to return the sequence which gave us the maximum sum...not just return the max sum. (Pl correct me if i got it wrong)

- vatson February 20, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vikas..
i understood that step... can u give me the sequences of previous step which he considered in arriving at 4,-4,8,-1. Is there any way to find the correct

- kiran February 20, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sourav February 20, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think Ajay's approach works in an array of negative values, say:
{-1,-2,-3,-4,-5}

in this case, we don't need to merge all continous -ves, but simply return -1.

Anyway, Ajay's is a good start...

- Cao March 05, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- MyNameIs March 06, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Refer to cormen for detailed solution to this problem.

nJoi

- Deepak March 06, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Khoa March 06, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}

- Hemant March 06, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

See, Khoas remark above, which references a O(n) algorithm described in Bentleys 'Programming Pearls.'

- Michael June 22, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Piyush Ranjan Satapathy April 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- James May 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above code returns {2,-8,3,-2,4} --- 4
but should return 5 (3,-2,4}

- Vamsi December 05, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

James, You have cleared all the confusion. Its clear and simple.
I was thinking through similar lines but missed on the partialsum concept.
thanks...

- Uma May 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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,

- JJ May 17, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The code will work

- Fred May 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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("}");

}

- vibhu May 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I tested with {-6,-10,-3,-2,-4}, your code generates -6, not -2.

- Kevin May 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}

- vibhu May 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vibhu May 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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("}");

}

- vibhu May 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- netrabbit June 09, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Kanna June 14, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Above solution can do this in O(n) .

- Kanna June 14, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the code given by james will not work when array contains all -ve numbers
and first negative is -1.

- sonurehal November 12, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Ramu November 26, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

counterexample:

{-2, 1, -1}
your solution returns: -1

- pavel.em June 10, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

- Varun Jobanputra January 12, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

{10,9,-1} Answer should be 19, whereas your code will return 18.

- Sukesh May 08, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is right!!
it returns 19...
sum is not the answer ... max is the answer

- Vamsi December 05, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

counterexample:

a = {-2, 1, -1}
your solution will return 0

- pavel.em June 10, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks a lot .....

- MAnoj January 24, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use dynamic programming. Keep the index to calculate the sum backwards. Since the middle number is added twice.

- Noname June 29, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}

- Anonymous October 01, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int largest(int[] arr){
	int sum= arr[0];
	int tempsum=0;
	for(int i=0;i<arr.length();i++){
		tempsum+=arr[i];
		if(tempsum>sum)
			sum=tempsum;
		if(tempsum<0)
			tempsum=0;
	}
	return sum;
}

- Vamsi December 05, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Sai Sura April 26, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my solution is to use dynamic programming, given, a1, ..., an,
sum[i] is the largest sum we find in sequence a1, .. ai
sum[i+1]= max(a[i+1], a[i+1]+sum[i])

- trojanhorse June 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
			}
		}

	}
}

- Anonymous June 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Some idiot thinks we all are compilers (sorry, but couldnt resist temptation after repeated informing people to not just paste 100s of lines of code dumbly; rather explain logic in 4 sentences.)

- Compiler June 04, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Classic problem. 10 line algo in programming pearls

- JD June 04, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Anonymous June 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Michael June 22, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Roy August 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
}
}

- MD February 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Two solutions:
1- interviewcodesnippets.com/?p=157
2- interviewcodesnippets.com/?p=165

- moe July 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Anonymous August 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

- nim September 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Sunny December 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }

- aalimian April 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
                    }
                }
            }

- ultrafish April 08, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More