Dynamic Programming is an obvious direction of thinking and also the
solution to this problem.
As far, I can only figure out a 3-dimensional DP algo for this
problem, demonstrated as below:
Assuming that the original array is A[1..n], n is the number of all
the elements in the array.
And we know all the different numbers in A[...]. we put them in a
rigorously increasing sequence B[1..p], where B[1] < B[2] < ... <
B[p-1] < B[p], and for every i from 1 to n, A[i] can be found in
B[1..p].
Define f(i, j, m) as the maximum sequence sum among all the
non-decreasing subsequences which 1) has a length of j elements, 2) is
within the subarray A[1..i] and 3) whose elements are all smaller than
or equal to B[m].
Then, we have the following recursive equations:
if (A[i] > B[m]) then f(i,j,m) = f(i-1,j,m)
else if (A[i] <= B[m]) and (we can easily find q that makes B[q] =
A[i] where q must be smaller than m) then f(i,j,m) = max{f(i-1,j,m),
f(i-1,j-1,q) + A[i]}
Taking all the boundary values into consideration, then we have a very
familiar DP algo, right?
On Thu, Aug 26, 2010 at 10:53 AM, Rahul <rv.wi...@gmail.com> wrote:
> @ bittu
>
> input : 6 1 4 8 3 7 k=2
> output : 6 + 8 =14
>
> it's not 7+8=15 which wud be the case if ul apply sorting and take k
> largest elements.
> if i got ur point correct.
>
>
>
>
> Rahul Verma
> NIT Allahabad
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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.
