|
208. Given an array like ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
208. Given an array like ......
Question:
Given an array like
[3,-6,2,10,-16,5]
Find the max consecutive sum.
Trivial solution is O(n^2).
for i=0 to n
for j=i to n
Find local max for the current i value among j values
Find the global max among local max values.
maybe an answer:
#include<iostream.h>
#include<conio.h>
void main()
{
int num[10],ct;
cout<<"Enter the number of elements:";
cin>>ct;
int start=-1,end=-1,len=0;
for (int i=0;i<ct;i++)
cin>>num[i];
int max_sum=num[ct-1];
int iter=ct-1;
for (iter=ct-1;iter>0;iter--)
{
int index=ct-1;
while (index-iter>=0)
{
int add=0;
for (int k=index;k>=index-iter;k--)
add=add + num[k];
if (add>max_sum)
{
start=index-iter;
end=index;
len=iter;
max_sum=add;
}
index--;
}
}
cout<<"Maximum Sum:"<<max_sum<<"\nStart at"<<start<<"\nEnd at:"<<end<<"\nLength: "<<len;
getch();
}
(Continued on next question...)
Other Interview Questions
| 