## Microsoft Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

No need of end variable....your program is giving wrong end point....replace the last statement from maxend=end to maxend=i and you will have correct end point.

No need of end variable....your program is giving wrong end point....replace the last statement from maxend=end to maxend=i and you will have correct end point.

int main()

{

int a[] = {1,-1,2,3,4,-10,1,7,8,4,5,6,-6};

int i,j,n = 13;

int maxSum = a[0];

int sum = a[0];

int sumStartIndex = 0;

int sumEndIndex = 0;

int curIndex = 0;

int maxSeqSum = a[0];

for(i = 1;i <n;i++)

{

sum = sum + a[i];

if(sum > maxSum)

{

maxSum = sum;

}

else if(sum < 0)

{

if(maxSeqSum < maxSum)

{

maxSeqSum = maxSum;

sumStartIndex = curIndex;

sumEndIndex = i - 1;

}

curIndex = i + 1;

maxSum = 0;

sum = 0;

}

}

printf("maxSeqSum = %d \t maxSum = %d \n",maxSeqSum,maxSum);

if(maxSeqSum < maxSum)

{

sumStartIndex = curIndex;

sumEndIndex = n - 1;

}

for(i = sumStartIndex;i <= sumEndIndex;i++)

printf("%d \t",a[i]);

return 0;

}

Look below the code in java. It will print the sequence which makes longest sequence.But first the array need to be sorted.

```
static void getMax(int[] a)
{
int len=a.length;
int insq=0;
int count=0;
int maxcount=0;
int startin=0;
int endin=0;
for (int i=0;i<len-2;i++)
{
if (a[i+1]==a[i]+1)
{
insq=1;
count=0;
int subcount=0;
while(a[i+1]==a[i]+1)
{
count+=a[i];
i++;
subcount++;
}
count+=a[i];
if(maxcount<count)
{
maxcount=count;
startin=i-1;
endin=i+subcount-1;
}
}
}
System.out.printf("Sequence= ");
/*System.out.println(endin);*/
for (int p=startin;p<=endin;p++)
{
System.out.print(a[p-1]);
System.out.print(",");
}
System.out.printf("maximum size=%s", maxcount);
}
```

#include<iostream.h>

void main()

{

int a[20], i = -1, max = 0, n, sum, maxi, maxj;

cout<<" enter the elements of the array";

do {

i++;

cin>>a[i];

}while ( a[i] != -9999 && i <19);

n = i;

for ( i = 0;i<n; i++) {

sum = 0;

for ( j = i +1; j<n; j++) {

sum =sum +a[j];

if ( sum>max) {

max = sum;

maxi = i;

maxj = j;

}

}

}

cout<<" Maximum continous sum:";

for ( i = maxi; i< maxj; i++)

cout<<a[i]<<'\t';

cout<<"The maximum sum is :"<<max;

}

```
int sum= 0, maxsum=0;
for(int i= 0; i< n; i++) //n is length of array
{
sum += a[i]; //a is array name
if( sum > maxsum)
maxsum = sum;
else if(sum < 0)
maxsum = 0;
}
```

the code is fine but in the "else if" when sum is less than 0 the "sum" should be set to 0 itself.

```
int maxSum(int a[])
{
int n=a.length;
int sum=0,maxSum=0;
for(int i=0;i<n;i++)
{
sum=sum+a[i];
if(sum>maxSum)
maxSum=sum;
else if(sum<0)
sum=0;
}
return maxSum;
}
```

/* Solution # 1 */

int findLargestSumSubArray(int arr[], int len, int& startIndex, int& endIndex)

{

int sum = 0;

int minSum = 0;

int minIndex = -1;

int subArrLargeSum;

subArrLargeSum = 0;

startIndex = -1;

endIndex = -1;

//iterating through the given array

for (int begin = 0; begin<len; begin++)

{

sum = sum + arr[begin];

if (sum <= minSum)

{

//saving the minimum sum and starting index

minSum = sum;

minIndex = begin;

}

if (sum - minSum > subArrLargeSum)

{

//starting index of sub array

startIndex = minIndex + 1;

//ending index of sub array

endIndex = begin;

//largest sum of sub array so far

subArrLargeSum = sum - minSum;

}

}

//Printing the sub array elements

if( subArrLargeSum <=0 || ((startIndex < 0) && (endIndex < 0)) )

{

printf("Numbers: No sub array, because sum of any sub array is less than or equal to zero\n");

}

else

{

int i = startIndex;

int j = endIndex;

//printing the sub array

//Note: this steps can be moved to main() function also

printf("Numbers: ");

while( i <= j)

{

printf("%d ", arr[i++]);

}

}

printf("\n\nStarting Index = %d\n", startIndex);

printf("Ending Index = %d\n\n", endIndex);

//returning the largest sum of sub array

return subArrLargeSum;

}

This algorithm scans an array from 0 to N-1 elements. When the largest sum of an array found, the algorithm will remembers the start and end index of that sub-array. An array is scanned only once. Hence, the time complexity of this algorithm is O(N).