[Inmobi]Maximum sum of increasing sequence
Variation of LIS:
Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example,
50,23,1,67,30 in this subsequence a few possible increasing subsequences are
1) 23,30
2) 23,67
2) 50,67
3) 1,67
4) 1,30
5) 67
6) 30
but 50, 67 gives the maximum sum. How to find it
Note: In the above scenario however if we have 128 at index 0 then it will have the max sum although it is not forming longest LIS.
Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example,
50,23,1,67,30 in this subsequence a few possible increasing subsequences are
1) 23,30
2) 23,67
2) 50,67
3) 1,67
4) 1,30
5) 67
6) 30
but 50, 67 gives the maximum sum. How to find it
Note: In the above scenario however if we have 128 at index 0 then it will have the max sum although it is not forming longest LIS.
int MSS_arr(int arr[],int size)
ReplyDelete{
int i=0,j=0,max_sum=0;
int* SUM=(int*)malloc(sizeof(int)*size);
for(i=0;i<size;i++)
{
SUM[i]=arr[i];
for(j=0;j<i;j++)
{
if((arr[j]<arr[i])&&(SUM[i]<SUM[j]+arr[i]))
{
SUM[i]=SUM[j]+arr[i];
}
}
}
for(i=0;i<size;i++)
{
if(max_sum<SUM[i])
max_sum=SUM[i];
}
return max_sum;
}
int lis( int arr[], int n )
ReplyDelete{
int *lis,*arr1, i, j, max = 0,max_value=0;
lis = (int*) malloc ( sizeof( int ) * n );
arr1 = (int*) malloc ( sizeof( int ) * n );
for ( i = 0; i < n; i++ )
lis[i] =1;
for ( i = 0; i < n; i++ )
arr1[i]=arr[i];
for ( i = 1; i < n; i++ )
{ for ( j = 0; j < i; j++ )
{ if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
{ lis[i] = lis[j] + 1;
if(lis[i] > max)
{ if (arr1[i] <(arr1[i]+arr1[j]))
arr1[i]=arr1[i]+arr1[j];
max=lis[i];
}
}
}
}
for(i=1;i < n;i++)
{ max_value=arr1[0];
if(arr1[i] > max_value)
max_value=arr1[i];
}
printf("\nThe Maximum sum is %d",max_value);
free( lis );
free( arr1 );
return max;
}