@rahul : nope it wont work ......check for this input :- input = 1, 2,3,6,4 ,101, 6
by removing msis[i] < msis[j] + arr[i] condition then you are excluding the max sub-sequence found from j=0 to i. On 10/21/12, rahul sharma <rahul23111...@gmail.com> wrote: > but if there are -ve numbers then arr[i]>arr[j] only is sufficeient as it > become false....comment if wrng > > On Sat, Oct 20, 2012 at 11:59 PM, Saurabh Kumar > <srbh.ku...@gmail.com>wrote: > >> If your inputs are only positive numbers then that condition you pointed >> out is indeed redundant. But if you want your program to work for >> negative >> numbers as well, you need that condition. >> Also, you should initialize max = msis[0]; before running the loop for >> calculating 'max' : >> >> >> /* Pick maximum of all msis values */ >> max = msis[0]; for ( i = 0; i < n; i++ ) >> if ( max < msis[i] ) >> max = msis[i]; >> >> >> On 20 October 2012 22:58, rahul sharma <rahul23111...@gmail.com> wrote: >> >>> http://www.geeksforgeeks.org/archives/19248 >>> /* Dynamic Programming implementation of Maximum Sum Increasing >>> Subsequence (MSIS) problem */ >>> #include<stdio.h> >>> >>> /* maxSumIS() returns the maximum sum of increasing subsequence in arr[] >>> of >>> size n */ >>> int maxSumIS( int arr[], int n ) >>> { >>> int *msis, i, j, max = 0; >>> msis = (int*) malloc ( sizeof( int ) * n ); >>> >>> /* Initialize msis values for all indexes */ >>> for ( i = 0; i < n; i++ ) >>> msis[i] = arr[i]; >>> >>> /* Compute maximum sum values in bottom up manner */ >>> for ( i = 1; i < n; i++ ) >>> for ( j = 0; j < i; j++ ) >>> if ( arr[i] > arr[j] && msis[i] < msis[j] + arr[i]) >>> msis[i] = msis[j] + arr[i]; >>> >>> /* Pick maximum of all msis values */ >>> for ( i = 0; i < n; i++ ) >>> if ( max < msis[i] ) >>> max = msis[i]; >>> >>> /* Free memory to avoid memory leak */ >>> free( msis ); >>> >>> return max; >>> } >>> >>> /* Driver program to test above function */ >>> int main() >>> { >>> int arr[] = {1, 101, 2, 3, 100, 4, 5}; >>> int n = sizeof(arr)/sizeof(arr[0]); >>> printf("Sum of maximum sum increasing subsequence is %d\n", >>> maxSumIS( arr, n ) ); >>> >>> getchar(); >>> return 0; >>> } >>> I wana ask inner for loop has two conditons ...cant we remove condition >>> onryt of && operator. >>> As miss[j] would containg arr[j]or arr[j]+somethng....if arr[i]>arr[j] >>> then miss[i] is always <miss[j]+arrp[i] >>> so cant we remove second condtion of && operator???? plz correct if m >>> wrng >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
