动态规划之求序列里最长的非降序列

求序列里最长的非降序列

例如：

输入：{5,3,4,8,6,7}

输出：4 即{3,4,6,7}
// maxnodecrease.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<vector>
#include<iostream>
using namespace std;

vector<int>maxnodecrease(int* input, int len, int startnumpos);
int findnext(int *in, int len, int numpos);
int findnew(int*in, int len, int firstnumpos, int secnumpos);
int _tmain(int argc, _TCHAR* argv[])
{
	const int len = 10;	 
	int a[len] = { 5, 2, 6, 4, 1, 1, 1, 6, 10, 9 };
	//int a[len] = { 2, 9, 3, 4, 5 };
	vector<int>::iterator it;
	vector<int>bb,cc;
	int maxlen = 0;
	for (int i = 0; i < len - 1; i++)
	{
		bb=maxnodecrease(a, len, i);
		if (bb.size()>maxlen)
		{
			maxlen = bb.size();
			cc = bb;
		}
	}
	for (it = cc.begin(); it != cc.end(); it++)
		cout << *it << endl;
	system("pause");
	return 0;
}

vector<int>maxnodecrease(int* input, int len,int startnumpos)
{
	vector<int>aa;
	aa.push_back(input[startnumpos]);
	int kk = findnext(input, len, startnumpos);
	int a = kk;
	while (kk)
	{
		aa.push_back(input[kk]);
		kk = findnext(input, len, kk);
	}
	int maxlen = aa.size();
	while(a)
	{
		a = findnew(input, len, startnumpos, a);
		if (a)
		{
			vector<int>cc;
			cc.push_back(input[startnumpos]);
			int bb = a;
			while (bb)
			{
				cc.push_back(input[bb]);
				bb = findnext(input, len, bb);
			}
			if (cc.size() > maxlen)
			{
				aa.clear();
				aa=cc;
			}
		}
	}
	return aa;
}

int findnext(int *in,int len, int numpos)
{
	int a = in[numpos];
	for (int i = numpos+1; i < len; i++)
	{
		if (in[i] >= a)
			return i;
	}
	return 0;
}


int findnew(int*in, int len,int firstnumpos, int secnumpos)
{
	for (int i = secnumpos + 1; i < len; i++)
	{
		if (in[i]>in[firstnumpos] && in[i] < in[secnumpos])
			return i;
	}
	return 0;
}