Saturday, April 24, 2010
Maximum sum
Given an array all of whose elements are positive numbers, find the maximum sum of a subsequent elements with the constraint that no 2 numbers in the sequence should be adjacent in the array. So, 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
Subscribe to:
Post Comments (Atom)
#include
ReplyDelete/*Function to return max sum such that no two elements
are adjacent */
int FindMaxSum(int arr[], int n)
{
int incl = arr[0];
int excl = 0;
int excl_new;
int i;
for (i = 1; i < n; i++)
{
/* current max excluding i */
excl_new = (incl > excl)? incl: excl;
/* current max including i */
incl = excl + arr[i];
excl = excl_new;
}
/* return max of incl and excl */
return ((incl > excl)? incl : excl);
}
/* Driver program to test above function */
int main()
{
int arr[] = {5, 5, 10, 100, 10, 5};
printf("%d \n", FindMaxSum(arr, 6));
getchar();
return 0;
}
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.
ReplyDeleteMax sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).
At the end of the loop return max of incl and excl.
No perfect algorithm or solution. Use greedy strategy.
ReplyDeleteex: find the Max element, then pick up next max element with the constraint that selected element should not be adjacent to previously selected elements. add up all the selected elements. repeat the process for all the elements
cant we do like
ReplyDeletefirst we get the sum of no at odd positions and than get the sum of numbers which are at even position and than get largest between them....
It's failing for simple case {1,3,5,7}
ReplyDeleteSort the array in increasing order of numbers and start summation from end of array taking summation of alternate numbers.
ReplyDeleteint bb[] = { 3, 2, 7, 10};
ReplyDeleteint cc[] = { 3, 2, 5, 10, 7 };
void
maxSum(int a[], int length)
{
int maxSum = 0;
for (int startingIt = 0; startingIt < length; startingIt++){
int it = startingIt;
int newMax = 0;
for (int indexStep = 2; indexStep < length; indexStep ++){
while (it < length){
newMax += a[it];
it += indexStep;
}
if (newMax > maxSum){
maxSum = newMax;
newMax = 0;
it = startingIt;
}
}
}
cout << "maxSum = " << maxSum << "\n";
}
int _tmain(int argc, _TCHAR* argv[])
{
//int arrLength = 5;
//maxSum(cc, arrLength);
int arrLength = 4;
maxSum(bb, arrLength);
}
hahah ... 10th me ho kya?
ReplyDeleteNagaraju:
ReplyDeletewe can't use odd and even positions.
{10,2,3,8}
Here Max sum is 18(10+8).
Here 10 is at odd position and 8 is at even position.
The solution to the above problem is dynamic programming. The recurrence relation is
ReplyDeletes(j)= max{s(j-2)+A[j],s(j-1)}
where, s(j) is the optimal solution up-to j'th position of the array.
It is an O(n) algorithm.
The code for this is:
#define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
void main()
{
int arr[]={3,2,5,10,7};
int size=sizeof(arr)/sizeof(int);
int i;
int *sum=(int*)malloc(sizeof(arr));
sum[0]=arr[0];
sum[1]=max(arr[0],arr[1]);
for(i=2;i<size;i++)
sum[i]=max(sum[i-2]+arr[i],sum[i-1]);
printf("%d",sum[size-1]);
}
// This is a greedy aproach
ReplyDeleteint max_non_consecutive_sum_before_index(int data[], int n)
{
int index = n-1;
if( index == 0 )
return data[index];
else if( index < 2 )
return (data[0]0; step_val++ )
{
int sum = data[index] + max_non_consecutive_sum_before_index(data, n-step_val);
if( max_sum < sum )
max_sum = sum;
}
return max_sum;
}
}
int max_non_consecutive_sum(int data[], int n)
{
if( n<= 2)
return max_non_consecutive_sum_before_index(data, n);
else
return std::max(max_non_consecutive_sum_before_index(data, n), max_non_consecutive_sum_before_index(data, n-1));
}
int _tmain(int argc, _TCHAR* argv[])
{
int data[100], n;
std::cout<<"Enter size: ";
std::cin>>n;
std::cout<<"Enter elements: "<>data[i];
std::cout<<"Max sum : "<<max_non_consecutive_sum(data, n)<<std::endl;
getch();
return 0;
}
//========= Sanish ====================
why cant we construct heap tree whose root is maximum element in array.
ReplyDeletewe pop up root element and again determine next highest element which index is not immediate to root element.