#include <iostream>
#include <vector>
#include <utility>
#include <iterator>
#include <string>
#include <sstream>
//#include "sequence_lister.h"

using namespace std;

#define INF 1000000000

class MaxMinGap {
    vector<int> x;
	int M;
	const int N;		// Just for convenience -- it's just x.size()
	vector<vector<int> > fMemo;
	vector<vector<int> > pred;		// Stores d values, from which the right i and j can be computed
	int bestM;
	
	// The following version finds solutions having *exactly* the given number of deletions,
	// which is what we need to get the right answer.
	int f(int i, int j) {
		if (i == N - 1) {
			if (j > 0) {
				return 0;		// The deletions won't all fit
			} else {
				return INF;
			}
		}
		
		if (fMemo[i][j] == -1) {
			int best = -1;
			int bestD = -1;
			for (int d = 0; d <= min(j, N - i - 2); ++d) {
				int guess = min(x[i + d + 1] - x[i], f(i + d + 1, j - d));
				if (guess > best) {
					best = guess;
					bestD = d;
				}
			}
			
			fMemo[i][j] = best;
			pred[i][j] = bestD;
		}
		
		return fMemo[i][j];
	}
	
public:
	MaxMinGap(vector<int> x, int M) : x(x), M(M), N(x.size()), fMemo(x.size() + 1, vector<int>(M + 1, -1)), pred(x.size() + 1, vector<int>(M + 1, -1)), bestM(INF) {
		solve();		// Might as well do it right away
	}
	
	// Must be called before getSolution() or getBestMinGapSize()
	void solve() {
		int best;
		for (int i = M; i >= 0; --i) {
			int guess = f(0, i);
			if (i < M && guess < best) {
				break;
			}
			
			best = guess;
			bestM = i;
		}
	}
	
	// The following version doesn't find the solution having the minimum number of deletions!
	//int f(int i, int j) {
	//	if (i == N - 1) {
	//		return INF;
	//	}
	//	
	//	if (fMemo[i][j] == -1) {
	//		int best = -1;
	//		int bestD = -1;
	//		for (int d = 0; d <= min(j, N - i - 2); ++d) {
	//			int guess = min(x[i + d + 1] - x[i], f(i + d + 1, j - d));
	//			if (guess > best) {
	//				best = guess;
	//				bestD = d;
	//			}
	//		}
	//		
	//		fMemo[i][j] = best;
	//		pred[i][j] = bestD;
	//	}
	//	
	//	return fMemo[i][j];
	//}
	
	// Wrongheaded!  Lacks optimal substructure on close inspection.
	//// The second element is the number of deletions that weren't needed, so
	//// that comparisons can be done with a simple ">".
	//pair<int, int> f(int i, int j) {
	//	if (i == N - 1) {
	//		return make_pair(INF, j);
	//	}
	//	
	//	if (fMemo[i][j].first == -1) {
	//		pair<int, int> best = make_pair(-1, -1);
	//		int bestD = -1;
	//		for (int d = 0; d <= min(j, N - i - 2); ++d) {
	//			pair<int, int> subproblem = f(i + d + 1, j - d);
	//			pair<int, int> guess;
	//			guess.first = min(x[i + d + 1] - x[i], subproblem.first);
	//			guess.second = subproblem.second;
	//			if (guess > best) {
	//				best = guess;
	//				bestD = d;
	//			}
	//		}
	//		
	//		fMemo[i][j] = best;
	//		pred[i][j] = bestD;
	//	}
	//	
	//	return fMemo[i][j];
	//}
	
	// solve() must be run first.
	int getBestMinGapSize() {
		return f(0, bestM);
	}
	
	// solve() must be run first.
	int getFewestDeletions() {
		return bestM;
	}
	
	// solve() must be run first.
	vector<int> getSolution() {
		vector<int> numbers;
		
		int i = 0, j = bestM;
		while (pred[i][j] != -1) {
			numbers.push_back(x[i]);
			int d = pred[i][j];
			i += d + 1;
			j -= d;
		}
		
		numbers.push_back(x[N - 1]);
		return numbers;
	}
};

// Function template for joining sequences into strings
template <typename C>
string list_sequence(C c, string delim) {
	ostringstream oss;
	for (typename C::const_iterator i(c.begin()); i != c.end(); ++i) {
		if (i != c.begin()) {
			oss << delim;
		}
		
		oss << *i;
	}
	
	return oss.str();
}

int main(int argc, char **argv) {
	cout << "Enter M (maximum number of numbers to delete): ";
	int M;
	cin >> M;
	cout << "\nEnter numbers (Ctrl-Z to end): ";
	MaxMinGap mmg(vector<int>(istream_iterator<int>(cin), istream_iterator<int>()), M);
	cout << "\nBest solution has a minimum gap size of " << mmg.getBestMinGapSize() << ", with " << mmg.getFewestDeletions() << " deletions needed.\n";
	cout << "Example optimal solution: " << list_sequence(mmg.getSolution(), " ") << ".\n";
	
	return 0;
}