longest decreasing sequnce of even numbers
OK HERE is my problem:
Let us consider a list a1,a2...an of integer numbers.Determine a longest decreasing sequence ai1,ai2..ajk consisting only of even numbers.Example: for the list 13,52,17,16,50,9,18,3 the solution is 52,50,18.(I really don t know if it's 100% "ai1...ajk"; I discovered in a book with very small writing but I think you have caught the idea).
I don't have to implement it, just to indicate the most appropiate programming method(greedy,dynamic programming,divide et impera,backtracking) that can be used for solving it and to justify the method's applicability and analyse the problem solving according to the particularity of the selected programming technique.
I've read some things on the internet and I've found that the programming method used in the problems like that is dynamic programming but this is all.
If anyone can give me some advices please share with me.Thank you!
Sounds like a dynamic programming problem. Specifically, this sounds like a variation of longest increasing subsequence. The Papadimitriou Algorithms textbook (which you can easily google online, but which I'm not allowed to post the link to here) offers a fundamental understanding of how to solve longest increasing subsequence. Page 162 I think. It's then pretty trivial to adapt the the algorithm to longest decreasing subsequence of evens.
- foxjas09 January 03, 2015