Algorithm required for this task?

Question

Inputs: n (int) and n values (float) that represent exchange rates (different between them) with a random value between 4 and 5.

Output: compute the maximum number of values that can be used (in the same order) to represent an ascending then descending curve?

---

e.x. The eight values

4.5 4.6 4.3 4.0 4.8 4.4 4.7 4.1

should output

5 (4.5 4.6 4.8 4.4 4.1)

---

My approach

• If I try successive ifs, I get a random array that respects the curve condition, but not the longest.
• I have not tried backtracking because I am not that familiar with it, but something tells me I have to compute all the solutions with it then pick the longest.
• And lastly: brute force, but since it is an assignment for algorithm design; I may as well not hand it in. :)

Is there a simpler/more efficient/faster method?

Here's my try based on Daniel Lemire's algorithm. It seems it doesn't take into account the positions 0, i and n. I'm sure the ifs are the problem, how can I fix them?

for(int i = 0; i<n-1; i++){
            int countp=0;   // count ascending
            int countn=0;   // count descending
            for(int j=0;j<=i;j++){
                    if(currency[j]<currency[j+1]){
                        countp++;
                        System.out.print(j+" ");
                    }
                }
            System.out.print("|| ");
            for(int j=i;j<n-1;j++){
                if(currency[j]>currency[j+1]){
                    countn++;
                    System.out.print(j+" ");
                }
            }
        System.out.println();
        if(countn+countp>maxcount) maxcount=countn+countp;                   
        }

Answer 1

Firstly, you want to be able to compute the longest monotonic subsequence from one point to another. (Whether it is increasing or decreasing does not affect the problem much.) To do this, you may use dynamic programming. For example, to solve the problem given indexes 0 to i, you start by solving the problem from 0 to 0 (trivial!), then from 0 to 1, then from 0 to 2, and so on, each time recording (in an array) your best solution.

For example, here is some code in python to compute the longest non-decreasing sequence going from index 0 to index i. We use an array (bbest) to store the solution from 0 to j for all j's from 0 to i: that is, the length of the longest non-decreasing subsequence from 0 to j. (The strategy used is dynamic programming.)

def countasc(array,i):
  mmin = array[0] # must start with mmin
  mmax= array[i] # must end with mmax
  bbest=[1] # going from 0 to 0 the best we can do is length 1
  for j in range(1,i+1): # j goes from 1 to i
    if(array[j]>mmax):
      bbest.append(0) # can't be used
      continue
    best = 0 # store best result
    for k in range(j-1,-1,-1): # count backward from j-1 to 0
      if(array[k]>array[j]) :
        continue # can't be used
      if(bbest[k]+1>best):
          best = bbest[k]+1
    bbest.append(best)
  return bbest[-1] # return last value of array bbest

or equivalently in Java (provided by request):

int countasc(float[] array,int i) {
    float mmin = array[0];
    float mmax = array[i];
    ArrayList<Integer> bbest= new ArrayList<Integer>();
    bbest.add(1);
    for (int j = 1; j<=i;++j) {
        if(array[j]>mmax){
            bbest.add(0);
            continue;
        }
        int best = 0;
        for(int k = j-1; k>=0;--k) {
            if(array[k]>array[j]) 
                continue;
            if(bbest.get(k).intValue()+1>best)
                best = bbest.get(k).intValue()+1;
        }
        bbest.add(best);
    }
    return bbest.get(bbest.size()-1);
}

You can write the same type of function to find the longest non-increasing sequence from i to n-1 (left as an exercise).

Note that countasc runs in linear time.

Now, we can solve the actual problem:

Start with S, an empty array
For i an index that goes from 0 to n-1 :
  compute the length of the longest increasing subsequence from 0 to i (see function countasc above)
  compute the length of the longest decreasing subsequence from n-1 to i
  add these two numbers, add the sum to S
return the max of S

It has quadratic complexity. I am sure you can improve this solution. There is a lot of redundancy in this approach. For example, for speed, you should probably not repeatedly call countasc with an uninitialized array bbest: it can be computed once. Possibly you can bring down the complexity to O(n log n) with some more work.

Answer 2

A first step is to understand how to solve the related longest increasing subsequence problem. For this problem, there is a simple algorithm that is O(n^2) though the optimal algorithm is O(n log n). Understanding these algorithms should put you on the right track to a solution.