top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+3 votes
782 views

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

posted Oct 11, 2014 by Harshita

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
Can you please give me sample input and output
Question updated, thanks.

2 Answers

+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;
}
answer Oct 13, 2014 by Balakrishnan S
0 votes

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

answer Jul 31, 2016 by Shahsikant Dwivedi
Similar Questions
+2 votes

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

0 votes

Given an unordered array A of size n and integer x. What is the best complexity to find two elements in A whose sum is x?
Share the algo, its complexity and if possible C code.

+4 votes

Write a program to make AVL tree buy arranging element in array ?

+8 votes

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

...