Identifying The Longest Upsequence

To construct a longest up-sequence, then there are various ways to do this. You could start at any element in the last stack: this is the last element in your up-sequence. You can now re-construct the longest up-sequence by selecting an element out of each of the stacks as follows: Take the previous stack, and find the largest element that is smaller than the element you just found; there is at least one such element, but there could be more.

This could be very time consuming (i.e. the algorithm has a high complexity), as many elements need to be popped from many stacks. To save yourself some ‘work’, you could also keep track of the information at the time that you

construct the stacks. This is explained through the example below, by storing the value of the top of the previous stack. For example, when 9 gets pushed onto stack 2, then the top of stack 1 at the time was 3. This information needs to be

maintained as well, and we stack ”3; 9 onto stack 2.

Required Output:

Given a sequence of natural numbers. You can expect between 1000 and 5000 numbers, each with a unique value between 1M and 2M. You are asked to find the length of the LUS, and to present two sequences:

1. The sequence, and the sum of the elements in this LUS sequence, which is obtained by following the pointers. It turns out that this subsequence takes the smallest value on each stack that would work. Its sum is thus smallest for all [login to view URL] for our last example, you would report ‘16, 17, 20, 21, 31, 34’, which sums to 139.

2. The sum of the elements in the LUS sequence obtained by finding the largest possible element on each stack that does not violate the ’upsequence’. So for our last example, you would report ‘16, 17, 20, 27, 31, 35’ which sums to 146

3. Furthermore, the elements in the first stack represents the longest decreasing subsequence that starts the first element. You are asked to report this length and it’s sum as well.

[login to view URL] (and report) the number of different subsequences. So for our last example, you report: There are a total of 6 different non-decreasing subsequences of length 6.

This is an immediate requirement Needed by July-8th 2015.

Java

Nº del proyecto: #8013764

Sobre el proyecto