longest decreasing sequence 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!

IMO, dynamic programming approach is best fit here. This problem is variation of longest increasing subsequence problem which can be easily solved using dynamic programming.
Solution of LIS is explained here :http://algorithmsandme.blogspot.in/2...ncreasing.html

Thanks

Quote:

---

Originally Posted by ashmidnight3223

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!

---

this can be solved with a single pass and creating a sequence tree with built in pruning as you go. when you're at the end you're left with the single longest branch.

there isn't an easy way to indicate "most apppropriate". It's usually the other way around, you eliminate the ones that can't possibly solve your problem adequately. THen either pick-and-pray your best guestimate from the remainder or try them all and pick the one that works best (which could be fastest, lowest memory usage, best "worse case", or any other or combination of factors).

Some problems can be solved with readily available algorithms, though they may need reformulation, or 'turning the problem upside down'.
Just because you can't find an algorithm/strategy to a particular puzzle, doesn't mean one doesn't exist :-p
and sometimes, the scope of problems is small enough that you can just brute force it. If it's a one off, then the ease of implementing brute force may get you an answer befor eyou have time to implement a better but more elaborate solution.

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.

ooh,but I really don't get it.Please give me a solution from my own problem if you know.

Quote:

---

Originally Posted by ashmidnight3223

if you know.

---

Well I have a suggestion that might work

The idea is to consider the numbers in reverse order, from last to first. All odd numbers are simply skipped since only even numbers are of interest.

A set of valid sequences is kept. During the reverse scanning, for each number it's checked whether this number can be put at the front of any of the existing sequences in the set keeping them valid still. It can if it's bigger than than the current first number of a sequence. If it can't be put in front of any of the existing sequences the number is added to the set as a new valid sequence with just one number.

When the reverse scanning process is over the longest sequence is picked from the set. It's the winner.

The above can be improved. If a number can be added in front of many valid sequences in the set ony the longest sequence (or sequences since there may be several equally long) needs to be kept in the set.

This is how it works with your test sequence: 13,52,17,16,50,9,18,3. I allow odd numbers to make it more interesting,

---
3 (first sequence in set)
---
18 3 (18 is bigger than 3 so it can be put in front of sequence)
---
18 3
9 (9 becomes a new sequence since it cannot be put in front of any other sequence)
---
50 18 3
50 9 (discarded since it can never beat the longer sequence also starting with 50)
---
50 18 3
16
---
50 18 3
17 16
---
52 50 18 3
52 17 16 (can be discarded)
---
52 50 18 3 (the winner)
13
---

It seems to work but I urge you to test it carefully (which I haven't).

Ok, and if you didn't allow the odd numbers then the first sequnce should have been 18 and not 3.

Quote:

---

Originally Posted by ashmidnight3223

Ok, and if you didn't allow the odd numbers then the first sequnce should have been 18 and not 3.

---

That's right. Whether you clear out the odd numbers before running the algorithm or disregad them while the algorithm is running won't matter. I kept the odd numbers only because I thought your test sequence would then be more illustrative.

In any case, with even numbers only your test sequence will effectively look like 52,16,50,18 and the algorithm will proceed like this,

---
18
---
50 18
---
50 18
16
---
52 50 18 (winner)
52 16 (can be discarded)
---

In my view the discarding of suboptimal sequences throughout the reverse scanning process makes this a dynamic programming algorithm. Keeping the optimum alternatives in each stage of a process is called the Bellman optimum principle. The basic idea of dynamic programming is that if a process is optimal at the first stage and in every stage after that, then it will also be optimal when it finishes.

Again, before depending on this algorithm, either confirm that it's a standard algorithm by finding a reference in the literature, or test it thouroughly.

ok,thank you very much!!:)