# WAP which outputs contiguous sequence whose sum is maximum in an array (It can have all negatives number too).

125 views

Input: arr[] = {5, 5, 10, -10, -20, 40, 50, 35, -20, -50}
Output: 125 (40, 50, 35)

posted Oct 11, 2014

Can you please give me sample input and output
Question updated, thanks.

+1 vote
``````#include <stdio.h>

int main(void)
{
int i,j,x,y,max=0,tem=0,v1,v2, arr[] = {15, 15, 120, 150, -250, 40, 50, 35, -20, -50},z,k;
int n=10; // length of array
k=n;
for(i=0;i<n;i++)
{
x=0;
y=k;
while(y<=n)
{
tem=0;
for(z=x;z<y;z++)
tem+=arr[z];
if(tem>max)
{
max=tem;
v1=x;
v2=y;
}
x++;
y++;
}
k--;
}

for(;v1<v2;v1++)
printf("%d\n" ,arr[v1]);
return 0;
}
``````

``````#include<stdio.h>
int main(){
int A[]={5, 5, 10, -10, -20, 40, 50, 35, -20, -50};
bool flag=0;
int startIndex=0,endIndex=0,maxSofar=0,maxEndHere=0,grtNegative=-328664,i;

for(i=0;i<10;i++){
maxEndHere+=A[i];
if(maxEndHere<0){
if(A[i]>grtNegative)
grtNegative=A[i];
maxEndHere=0;
flag=0;
startIndex=0;
}
if(maxEndHere>maxSofar){
maxSofar=maxEndHere;
if(!flag){
startIndex=i;
flag=1;
}
endIndex=i;
}
}
//printing the set with maximum sum
if(startIndex!=0 && endIndex!=0)
for(i=startIndex;i<=endIndex;i++)
printf("%d ",A[i]);
else
printf("%d",grtNegative);
return 0;
}
``````

Time Complexity= O(n)

Similar Questions

consider an example :
if an array is: 2 -1 2 4 6 -5
then maximum sum of contiguous array is 13, from index 0 to index 4
constraints: complexity must not be greater than O(n).