Given array of positive integer, find the largest member c in array such that c=a+b,where a and b are elements of the array.
Code:
#include <stdio.h>
#include <stdlib.h>
/* Comparator function */
int compare(const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int maxsum(int a[], int n)
{
qsort(a, n, sizeof(int), compare);
int i, j;
while(n--)
{
i = 0;
j = n - 1;
while(i < j)
{
int sum = a[i] + a[j];
if(sum == a[n])
return sum;
if(sum > a[n])
j--;
else
i++;
}
}
return -1;
}
int main()
{
int ar1[] = {14, 8,1, 12,27,15,6,13,21};
int n1 = sizeof(ar1)/sizeof(ar1[0]);
printf("Maximum sum is %d", maxsum(ar1, n1));
getchar();
return 0;
}
#include <assert.h>
ReplyDeleteint maxsum(int *a, int n) {
/* Given array of integer,
* find the largest number c such that c=a+b,
* where a and b are unique elements of the array.
*/
/* This code is better than SUDHANSU for four reasons
* - Check that the array has at least two entries
* - Works in O(n) time, SUDHANSU O(n lg n)
* - Does not have side effect of modifying or rearranging the array
* - Does not muck a[n] when we should use a[0] ... a[n-1]
*/
/* The largest sum of any two is the sum of the two largest */
assert(n > 1);
int x = *a++, y = *a++;
n -= 2;
while (n--) {
int z = *a++;
if (z > x) x = z;
else if ( z > y) y = z;
}
return x + y;
}
Note that question says c should also be member of array. Hence your solution doesnt output Correct value for array taken in Code. Correct answer is 27. Your Code prints 48, which is not there in array
Delete