CareerCup

The simplest and the worst performing solution is to exhaustively compute the subsequences and determine the one with the largest sum. A NxN matrix can be used for storage where matrix[i,j] would be the sum of subsequence [i to j]. N is the number of elements in the array.

O( N^2 )

Could someone please suggest a better algorithm?

This question has been discussed before.

http://www.careercup.com/question/?q=1d59aabd-8c9d-4915-8e0c-16bcaf83ce92

This particular problem is called finding maximum subsequence problem and is a very common problem in data structures and algorithms.
the best poosible solution to this could be something like as follows:-

int maxsubsequence(int a[],int N) /*returns 0 if all entries in the array are negative*/
{
int ThisSum=0;
int MaxSum = 0;
for(int j=0;j<N;j++)
{
ThisSum = ThisSum + A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
if(ThisSum <0)
ThisSum = 0;
}
return MaxSum;
}

My messy solution to this problem..

#include<stdio.h>
void main()
{
	int i, n, sum=0, prev_sum = 0, a[100], smallest_negative, start_index, end_index, prev_start_index, prev_end_index,smallest_index;
	printf("Enter the number of elements in the array \n");
	scanf("%d", &n);
	printf("Enter the elements of the array \n");	
	for(i = 0;i<n;i++)
		scanf("%d", &a[i]);
	smallest_negative = a[0];
	start_index = 0; 
	end_index = 0;
	prev_start_index = 0;
	prev_end_index = 0;
	smallest_index = 0;
	for(i=0;i<n;i++)
	{
		if(smallest_negative < a[i])
		{
			smallest_negative = a[i];
			smallest_index = i;
		}
		if(sum + a[i] < sum && prev_sum < sum)
		{
			prev_end_index = i-1;
			prev_start_index = start_index;
			prev_sum = sum;
		}
		sum = sum + a[i];
		if(sum < 0)
		{
			sum = 0;
			start_index = i+1;
		}
		else
			end_index = i;
	}
	
	if(sum < prev_sum)
	{
		start_index = prev_start_index;
		end_index = prev_end_index;
	}
	sum = (sum > prev_sum)?sum:prev_sum;
	if(!sum)
	{
		sum = smallest_negative;
		start_index = end_index = smallest_index;
	}
	printf("The maximum sum in the array is %d ", sum);
	printf("The elements are \n");
	for(i=start_index;i<=end_index;i++)
		printf("%d ", a[i]);
}

Sunaina was wrong to just scan the array once.
I can seem understand what Qauravk was doing:
if(smallest_negative < a[i])
{
smallest_negative = a[i];
smallest_index = i;
}
Look like it is finding the largest negative(smallest absolute value) if a[i] is negative.

The algorithm should like the following;
1. Scan the array once, find the first positive number a[i] and the last posotove a[j]. Clearly, the maximum subsequence(MSQ) sum is between these two. At the same time we count the numbers of non-positives and the largest non-positive a[k].
a) No positive exists. a[k] itself is the MSQ;
b) Only one positive a[i], it is MSQ;
c) At least two positives a[l] and a[j]. The MSQ is between a[i] and a[j].
Now, the question becomes: find MSQ for array a[], i = 0 to m-1, and a[0], a[m-1] > 0.

As someone mentioned above the answer to this is in cc book & discussed else where.

I was asked at MS about this & gave them the answer from the book which was good, but the 1 thing interviewer pointed out was with regards to edge case of having a MAX_NUM stored in the array & adding a +ve num to it, can result in Int overflow, so be careful of things like that not just for this problem, but other problems too. The answers you get from book are just for solving the regular case & don't cover some edge cases

Using the kadance algorithm we can solve this problem