Microsoft Interview Question
Software Engineer / DevelopersCountry: 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).