一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列被称为

摇摆序列。一个小于2个元素的序列直接为摇摆序列。给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度：

输入[1,17,5,10,13,15,10,5,16,8]，结果为7([1,17,10,13,10,16,8] )

序列 [1, 7, 4, 9, 2, 5]，相邻元素的差 (6, -3, 5, -7, 3)，则为摇摆序列，结果为6

序列 [1,4,7,2,5] (3, 3, -5, 3)、 [1,7,4,5,5] (6, -3, 1, 0)不是摇摆序列，结果为2

根据贪心算法的核心：

1. 寻找数据规律
2. 使用最优的迭代策略

分析：

• 规律
  
  很明显，摇摆序列的判定并不支持存在连续三个或者更多元素是递增或者递减的情况；需要连续三个元素中处于中间的元素要么比两边的元素小，要么比两边的元素大
• 迭代策略
  
  当出现连续三个或者更多元素是递增/递减的情况时，选择最优（最后一个递增/递减的元素作为可以假如摇摆序列的转折点，因为最后一个元素最大/最小，相比与下一个元素，有更大的可能使得其也满足摇摆序列）
  
  比如[1,17,5,10,13,15,10,5,16,8] 中 [10,13,15] 三个连续递增，那么选择15则会使得下一个10也能够满足成为摇摆序列中的元素

实现算法（文末有完整测试代码）:方法一

/*if..else if .. else */
int get_swing_seq(vector<int> &seq) { if(seq.size() <= 1) { return seq.size();}int max_len = 1;int i;for (i = 1; i < seq.size()-1; ++i) { if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) {  //满足递减转折时max_len ++;} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) { //满足递增转折时max_len ++;}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) { max_len ++;} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) { max_len ++;}return max_len;
}

实现算法：方法二

状态机的方式：

/*state machine: BEGIN,UP,DOWN*/
int get_swing_seq2(vector<int> &seq) { if(seq.size() <= 1) { return seq.size();}static const int BEGIN = 0;static const int UP = 1;static const int DOWN = 2;int STATE = BEGIN;int max_len = 1;for (int i = 1;i < seq.size(); ++i) { switch (STATE){ case BEGIN:if(seq[i-1] > seq[i]) { STATE = DOWN;max_len ++;} else if (seq[i-1] < seq[i]) { STATE = UP;max_len ++;}break;case UP:if(seq[i-1] > seq[i]) { STATE = DOWN;max_len ++;}break;case DOWN:if(seq[i-1] < seq[i]) { STATE = UP;max_len ++;}break;default:break;}}return max_len;
}

实现算法：打印摇摆序列

/*if..else if .. else; return the result seq */
vector<int>  get_swing_seq3(vector<int> &seq) { if(seq.size() <= 1) { return seq;}vector<int> seq_result;int i;seq_result.push_back(seq[0]);for (i = 1; i < seq.size()-1; ++i) { if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) { seq_result.push_back(seq[i]);} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) { seq_result.push_back(seq[i]);}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) { seq_result.push_back(seq[i]);} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) { seq_result.push_back(seq[i]);}return seq_result;
}

测试代码：

#include 
#include 
#include using namespace std;/*if..else if .. else */
int get_swing_seq(vector<int> &seq) { if(seq.size() <= 1) { return seq.size();}int max_len = 1;int i;for (i = 1; i < seq.size()-1; ++i) { if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) { max_len ++;} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) { max_len ++;}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) { max_len ++;} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) { max_len ++;}return max_len;
}/*if..else if .. else; return the result seq */
vector<int>  get_swing_seq3(vector<int> &seq) { if(seq.size() <= 1) { return seq;}vector<int> seq_result;int i;seq_result.push_back(seq[0]);for (i = 1; i < seq.size()-1; ++i) { if(seq[i-1] > seq[i] && seq[i] < seq[i+1]) { seq_result.push_back(seq[i]);} else if(seq[i-1] < seq[i] && seq[i] > seq[i+1]) { seq_result.push_back(seq[i]);}}/*handle the last element*/if(seq[i-2] > seq[i-1] && seq[i-1] < seq[i]) { seq_result.push_back(seq[i]);} else if(seq[i-2] < seq[i-1] && seq[i-1] > seq[i]) { seq_result.push_back(seq[i]);}return seq_result;
}/*state machine: BEGIN,UP,DOWN*/
int get_swing_seq2(vector<int> &seq) { if(seq.size() <= 1) { return seq.size();}static const int BEGIN = 0;static const int UP = 1;static const int DOWN = 2;int STATE = BEGIN;int max_len = 1;for (int i = 1;i < seq.size(); ++i) { switch (STATE){ case BEGIN:if(seq[i-1] > seq[i]) { STATE = DOWN;max_len ++;} else if (seq[i-1] < seq[i]) { STATE = UP;max_len ++;}break;case UP:if(seq[i-1] > seq[i]) { STATE = DOWN;max_len ++;}break;case DOWN:if(seq[i-1] < seq[i]) { STATE = UP;max_len ++;}break;default:break;}}return max_len;
}int main(){ vector<int> seq;int tmp;cout << "input seq " << endl;for (int i = 0;i < 10; ++i) { cin >> tmp;seq.push_back(tmp);}cout << "max of the swing seq len is " << get_swing_seq2(seq) << endl;vector<int> result = get_swing_seq3(seq);cout << "max of the swing seq is ";for (int i = 0;i < result.size(); ++i){ cout << result[i] << " ";}return 0;
}

输出如下:

input seq 
1 17 5 10 13 15 10 5 16 8
max of the swing seq len is 7
max of the swing seq is 1 17 5 15 5 16 8