If we have an array of Interger values, find out a sub array
which has a maximum value of the array and start and end
positions of the array..The sub array must be contiguious.
Take the start add to be 4000.
For Ex if we have an array arr[] =
{-1,-2,-5,9,4,3,-6,8,7,6,5,-3}
here the sub array of max would be
{8,7,6,5} coz the sum of max contiguous array is 8+7+6+5 =
26.The start and end position is 4014(8) and 4020(5).
- 5 Answers
- 10397 Views
- Microsoft, Motorola, I also Faced
- E-Mail Answers
Answer Posted / kyle
Here's another way...
Btw this way gets the correct answer of {9,4,3,-6,8,7,6,5}
with a sum of 36.
#include <stdio.h>
#include <stdlib.h>
#ifndef NULL
#define NULL 0
#endif
struct index {
int start;
int finish;
int sum;
};
int main()
{
// Init and setup variables
struct index max; // Max values
struct index cur; // Current values
int avg = 0; // Average values
int len = 0; // Array length
int* a = NULL; // The array
int i;
//Get values
printf("Enter the number of variables in the array:");
scanf("%d", &len);
array = malloc(len*sizeof(int));
if( array == NULL )
{
printf("Error: Out of memory");
return 0;
}
for(i=0; i<len; ++i)
{
scanf("%d",&a[i]);
avg += a[i];
}
avg /= len; // Compute average
max.start = max.finish = 0;
max.sum = a[0];
for(i=0; i<len && max.finish != len; ++i)
{
cur.start = cur.finish = i;
cur.sum = a[i];
while( cur.sum > avg && cur.finish < len )
{
if( cur.sum > max.sum )
{
max.start = cur.start;
max.finish = cur.finish;
max.sum = cur.sum;
}
++cur.finish;
if( cur.finish < len )
cur.sum += a[cur.finish];
}
}
printf("\n Max sum = %d, start = %d, finish = %d\n",
max.sum, max.start, max.end);
return 0;
}
| Is This Answer Correct ? | 1 Yes | 2 No |
Post New Answer View All Answers
What is the acronym for ansi?
An application package has been provided to you without any documents for the following application. The application needs to be tested. How will you proceed?
What is a spanning Tree?
write a C program:There is a mobile keypad with numbers 0-9 and alphabets on it. Take input 0f 7 keys and then form a word from the alphabets present on the keys.
What language is c written?
Is main a keyword in c?
Q.1 write a program to create binary tree 1 to 16 numbers? Q.2 write a program to creat a binary search tree for the member that is given by user?
i got 75% in all semester am i eligible for your company
Where register variables are stored in c?
What is the scope of local variable in c?
What is function definition in c?
writ a program to compare using strcmp VIVA and viva with its output.
Write a program of advanced Fibonacci series.
What are the types of type qualifiers in c?
Describe the complexity of Binary search, Quicksort and various other sorting and searching techniques..
