## Saturday, February 18, 2012

### Maximum Sum Increasing Subsequence

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.

Code:
int lis( int arr[], int n )
{
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;
}

1. http://people.csail.mit.edu/bdean/6.046/dp/

2. Hey,

1. Why the statement
"max_value=arr1[0];"
is placed inside the last for-loop?

In that way the code won't find max in arr1, it'll find the last one greater than arr1[0].

2. Inside the embedded loop, shouldn't it be
"if (arr1[1]<(arr[i]+arr1[j])) {arr1[i]=arr[i]+arr1[j]}"?
It seems for this sequence "4, 1, 2, 5", arr1[3] is 5 when i becomes 3, after one iteration of the inner loop, it becomes 9. When j is 1, nothing changes. When j is 2, <1, 2, 5> is found as the LIS and arrq[3] is changed into 12.

3. I understand the embedded loop part, but if you're only asked to find the max sum of any increasing subsequence, should
"if (arr[i]>arr[j] && arr1[j]+arr[i]>arr1[i])" be sufficient ?