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).
Answers were Sorted based on User's Feedback
Answer / monica
Well this is not an answer to the question but the solution
given in the example is wrong. Wont the subarray that gives
the max sum be {9,4,3,-6,8,7,6,5} whose sum is 36???
Is This Answer Correct ? | 8 Yes | 0 No |
Answer / sowmya
# include<stdio.h>
int main()
{
int i,j,k,sum[30],l,z =0,num = 0,sub,len;
int a[30],index[15][15],temp;
sum[z] = 0;
printf("\n Enter the Max.no. of elements to be
entered in the array :\n");
scanf("%d",&len);
printf("\n Enter the array Values : \n");
for(i=0;i<len;i++)
scanf("%d",&a[i]);
for(i = 0;i <len;i++)
{
k = len/2;
l = i+k;
for(j=i;j<l;j++)
if(j<len)
{
num++;
}
if(num == k)
{
for(j =i;j<l;j++)
{
if(j<len)
sum[z] = sum[z]+a[j];
else printf("\n num <3!");
}
z++;
sum[z] = 0;
}
num = 0;
}
j = 0;
for(i = 0 ;i <z;i++)
{
printf(" sum[%d] = %d\n",i,sum[i]);
index[j][i] = sum[i];
}
for(i = 0;i<z;i++)
{
for(j = i+1;j<z;j++)
if(sum[i] < sum[j])
{
temp = sum[i];
sum[i] = sum[j];
sum[j] = temp;
}
}
j= 0;
for(i = 0;i<z;i++)
if(index[j][i] == sum[0])
sub = i;
printf(" Sub array of max. sum = { ");
for(i = sub;i<sub+k;i++)
printf(" %d ",a[i]);
printf("}");
return 0;
}
Is This Answer Correct ? | 2 Yes | 2 No |
Answer / manoj
Another approach
# include<stdio.h>
struct index {
int sum;
int start;
int end;
};
int main()
{
struct index sumidx[30],*tmp;
int i,j,z =0,len;
int a[30];
printf("\n Enter the Number of elements to be entered
in the array :\n");
scanf("%d",&len);
printf("\n Enter the array Values : \n");
for(i=0;i<len;i++)
scanf("%d",&a[i]);
for(i = 0;i <len - 1;i++)
{
sumidx[z].sum = a[i];
sumidx[z].start = i;
sumidx[z].end = i;
for(j=i+1;j<len;j++)
if(sumidx[z].sum < (sumidx[z].sum + a[j]))
{
sumidx[z].sum = sumidx[z].sum + a[j];
sumidx[z].start = i;
sumidx[z].end = j;
}
else
break;
z++;
}
tmp = sumidx;
for(i = 0;i<z;i++)
{
if(sumidx[i].start != sumidx[i].end)
if(tmp->sum < sumidx[i].sum)
tmp = sumidx+i;
}
printf("\n sum = %d start = %d end
%d\n",tmp->sum,tmp->start,tmp->end);
return 0;
}
Is This Answer Correct ? | 2 Yes | 2 No |
Answer / vadivelt
Hi All,
I hope the code which i have written ll give the exact
answer
Note: Compiler used is visual Studio 2005
Eg: if the the no of elemet is 12 and the elements are -1,-
2,5,6,-4,7,8,9,-3,10,20,-4 then output(sub array) should
contain the elements 10
and 20.
#include<stdio.h>
#include<conio.h>
int MakeSubArray(int *ptr, int size);
main()
{
int array[100];
int subarray[10], Index, no, j, k;
printf("ENTER NO OF ELEMENTS IN THE MAIN ARRAY \n");
scanf("%d", &no);
printf("\nENTER THE ELEMENTS\n");
for(j = 0; j<no; j++)
{
scanf("%d", &array[j]);
}
Index = MakeSubArray(&array[0],no);
printf("\nSTART POSITION\n%d", &array[Index]);
printf("\n\nSUB ARRAY ELEMENT(S) \n");
for(j = Index, k = 0; (array[j] >= 0) && (j < no);
j++, k++)
{
subarray[k] = array[j];
printf("%d ", subarray[k]);
}
printf("\n\nEND POSITION\n%d", &array[j-1]);
getch();
}
int MakeSubArray(int *ptr, int size)
{
int i, flag = 0, sum = 0, sum1 = 0, index = 0,
index1;
if(ptr != '\0' && size > 0)
{
for(i = 0; i <size; i++)
{
if(ptr[i] >= 0)
{
if(flag == 0)
{
index = i;
}
sum = sum + ptr[i];
flag++;
}
else
{
if(flag > 0 && sum1 < sum)
{
index1 = index;
sum1 = sum;
}
sum = 0;
flag = 0;
}
}
/*If the last element is non zero and it is part of
sub array then this condition is useful*/
if(flag > 0 && sum1 < sum)
{
index1 = index;
}
}
return index1;
}
Is This Answer Correct ? | 1 Yes | 1 No |
Answer / 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 |
I need previous papers of CSC.......plz help out by posting them.......
#include <stdio.h> #define sqr(x) (x*x) int main() { int x=2; printf("value of x=%d",sqr(x+1)); } What is the value of x?
16 Answers Accel Frontline, Opera, Oracle,
to print the salary of an employee according to follwing calculation: Allowances:HRA-20% of BASIC,DA-45% of BASIC,TA-10%. Deductions:EPF-8% of BASIC,LIC-Rs.200/-Prof.Tax:Rs.200/- create c language program?
Find greatest number out of 10 number without using loop.
How to add two numbers with using function?
How can you tell whether two strings are the same?
Is register a keyword in c?
what are bps & baud rates? differentiate these two?
What is #define used for in c?
What is the c language function prototype?
When is a “switch” statement preferable over an “if” statement?
How can I get the current date or time of day in a c program?