A sequence X[1..m] of integers is said to be convex if X[i+1] - X[i] > X[i] - X[i-1] for every integer i between 2 and m-1. Thus, the sequence [0, 1, 3, 7, 12, 20] is convex, and so is [5, 3, 2, 2, 4, 8]. On the other hand, [0, 3, 7, 8, 13] is not convex because 8 - 7 < 7 - 3.

Note that a sequence with 0, 1, or 2 integers is convex by definition. Here is another way of thinking about convex sequences. Given X[1..m], define Y[2..m] by letting Y[i] = X[i] - X[i-1]. Thus, Y is the sequence consisting of differences between successive terms of X. The sequence X is convex if and only if the sequence Y is increasing.

The name convex comes from the fact that is we plot the points (i, X[i]) in the plane, one gets a convex shape.

The algorithmic problem we wish to solve is this. We are given as input a sequence A[1..n] of non-negative integers, and we wish to find a longest convex subsequence of A. For example, if A = [0, 3, 7, 8, 13], then a longest convex subsequence is [0, 3, 7, 13]. Here is a file that shows the format in which the input data is given. The first line specifies n, the length of the input sequence A. The next n lines specify the integers in A, in the order in which they occur in A.

Write a program that asks for an input file that contains the input sequence A in the above format, and outputs the length of the longest convex subsequenceof A, followed by a longest convex subsequence. For full credit, your program should be able to correctly solve inputs of length up to 100 reasonably fast, say within a second to ten minutes. Your program should be sequential, that is, it should not resort to any kind of parallelism like threads, GPU, etc. We want to keep the focus on algorithmic ideas in the sequential setting. We will accept programs in Python, Java, C, and C++.

This assignment corresponds to Exercise 4(f) of Chapter 2 and Exercise 7(f) of Chapter 3 in Jeff Erickson's textbook. That should tell us that there is a nice solution using the methods of those two chapters!

The homework is due Monday, March 25, at 11:59 pm. It is worth 60 points.

Submission Instructions:

Please submit a document that (a) describes your algorithm and any data structures you use in your implementation; (b) the running time in milliseconds on the test inputs of length 100 below, and (c) instructions for running your program. In addition, submit the program. All submissions are to be done on ICON.

Your algorithm description should be detailed enough that we should not have to read your code. When calculating running time, exclude the time for reading in the data from the input file.

Sample Inputs

Test Inputs (posted 4/2)