Sorry, this is not a good example. Try this: Assuming the sequence is 2, 1, 1, 1 and k = 3. The correct answer will be 1, 1, 1. Run your code and see the result.
On Sat, Aug 28, 2010 at 1:54 PM, satish <[email protected]> wrote: > @Adam > i ran the program with n=4 and k=2 and sequence as 2,3,999,9999 > i got 10998(i.e999+9999). > plz check it.... > > On Sat, Aug 28, 2010 at 10:25 AM, Adam <[email protected]> wrote: >> >> Actually, your code just considers the only non-decreasing subsequence >> which starts from a[0] and is the most 'LEFT' one in this situation >> rather than all the possible subsequences. >> >> For example, we have such sequence as 2,3,999,9999, and k = 2. >> >> In this situation, your code will give the subsequence {2,3} as the >> result rather than the true one {999,9999}. >> >> On Aug 28, 3:36 am, satish satish <[email protected]> wrote: >> > @Rahul >> > >> > #include<stdio.h> >> > #include<stdlib.h> >> > int nondecresing_maxsum(int *a,int n,int k) >> > { int sum=0,i,count=k+1,prev_num=a[0],*dp,count1=0;; >> > dp=(int *)malloc(sizeof(int)*(k+1)); >> > for(i=0;i<n;++i) >> > if(prev_num<=a[i]) >> > { sum+=a[i]; >> > prev_num=a[i]; >> > dp[count1%(k+1)]=a[i]; >> > count1++; >> > count--; >> > if(!count) >> > { sum-=dp[(count1)%(k+1)]; >> > count++; >> > } >> > } >> > return sum;} >> > >> > int main() >> > { int *arr,arr_size,i,k; >> > printf("give array size and k"); >> > scanf("%d%d",&arr_size,&k); >> > arr=(int *)malloc(sizeof(int)*(arr_size+1)); >> > printf("give elements"); >> > for(i=0;i<arr_size;++i) >> > scanf("%d",&arr[i]); >> > printf(" %d",nondecresing_maxsum(arr,arr_size,k)); >> > >> > } >> > >> > this is my first post >> > plz correct me if im wrong.... >> > but this wil not work if all array numbers r negetive... >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
