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

向右看齐 2022-08-02 00:28 146阅读 0赞

求序列里最长的非降序列   
  
  
例如：  
  
  
输入：\{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;
    }