求最长递减子序列，用栈进行处理

代码如下：

// getDecreaseSub.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>using namespace std;/*求一个数组的最长递减子序列比如{9，，，，，，，}的最长递减子序列为{9，，，，}*/#include <stack>using namespace std;static stack<int> helper;void SortStack(int * arr, int pos, int maxLen ) {int i;while(!helper.empty() && helper.top()<arr[pos])helper.pop();for (i = 0;i<maxLen;i++){helper.push(arr[i+pos]);}}void getDecreaseSub(int *arr,int arrLen ){int maxLen = 0;  //保存递减子序列长度int pos = 0;     //保存最长递减子序列的终止位置int len =1;for (int i=1;i<=arrLen;i++){if (i<arrLen && arr[i] < arr[i-1]){len++;}else {if (len >= maxLen){maxLen = len;SortStack(arr,pos,maxLen);  //调整栈中数据}len = 1;pos = i;}}}int main(){//int arr[] = {13,9,11,10,6,9,8,7,6};//int arr[] = {3,4,-1,2,0,9};int arr[] = {9,4,3,2,5,4,3,2};int arrLen = sizeof(arr)/sizeof(int);int i;int maxLen=0;for(i=0;i<arrLen;i++){if (i<arrLen-1){cout<<arr[i]<<" ,";}else cout<<arr[i]<<endl;}cout<<"最长递减子序列是：";getDecreaseSub(arr,arrLen);while(!helper.empty()){cout<<helper.top()<<"   ";helper.pop();maxLen++;}cout<<endl;cout<<"最长递减子序列是："<<maxLen<<endl;system("pause");return 0;}