yes got it......thnx :d On Sun, Oct 21, 2012 at 4:19 PM, atul anand <atul.87fri...@gmail.com> wrote:
> @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. > > -- 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.
