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

Question

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

Comments

Can you please give me sample input and output

---

Question updated, thanks.

Answer 1

#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;
}

Answer 2

//you can use kadane's algorithm:

#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)