程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 最長有序子串的C++實現代碼

最長有序子串的C++實現代碼

編輯:C++入門知識

//子串和子序列的區別是子串是連續的,子序列可以不連續

#include <iostream>
#include <vector>

using namespace std;

void MaxOrderedSub(const vector<int> &data)
{
     int num=data.size();
//用輔助數組記錄以i結尾最長子串長度
     vector<int> array(num,1);
     for(int i=1;i<num;i++)
     {
        if(data[i]>data[i-1])
            array[i]=array[i-1]+1;
     }

     int result=0;
     int last=0;

//找到array中的最大值便是最長序列長
//last為這array中的下標,也就是最長序列的終點
    for(int k=0;k<num;k++)
    {
        if(array[k]>result)
        {
            result=array[k];
            last=k;
        }
    }

    cout<<"the long of the sequence:"<<result<<endl;
    cout<<"the sequence:"<<endl;

    for(int j=last;array[j]!=1;j--);
    for(i=j;i<=last;i++)
        cout<<data[i]<<" ";
    cout<<endl;
}

int main()
{
    cout<<"input the size of the array:"<<endl;
    int num;
    cin>>num;
    vector<int> arr(num,0);
    for(int i=0;i<num;i++)
        cin>>arr[i];
    MaxOrderedSub(arr);
    return 1;
}

 作者“冒大煙的羊肉串的專欄”

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved