求最大成绩连续子序列

佚名 6年前 (2019-05-04) 随笔 1742人围观抢沙发百度已收录

考虑到正负号的问题，显然一个动态规划的表不够，于是用两个表来进行dp

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<vector>
 4 using namespace std;
 5 int main(void)
 6 {
 7     int n = 0;
 8     while (cin >> n)
 9     {
10         vector<int> seq;
11         int i=0;
12         int num;
13         while (i <= n-1 )
14         {
15             cin >> num;
16             seq.push_back(num);
17             ++i;
18         }
19         int size = seq.size();
20         if (size == 0)
21             return 0;
22         vector<int> dp(size + 1, 0);
23         vector<int> max_(size + 1, 0);
24         vector<int> min_(size + 1, 0);
25         int j = 0;
26         dp[0] = seq[0];
27         max_[0] = seq[0];
28         min_[0] = seq[0];
29         int result = 0;
30 
31         for (i = 1; i <= size - 1; ++i)
32         {
33             max_[i] = max(seq[i], max(max_[i - 1] * seq[i], min_[i - 1] * seq[i]));
34             min_[i] = min(seq[i], min(max_[i - 1] * seq[i], min_[i - 1] * seq[i]));
35             if (max_[i] > result)
36                 result = max_[i];
37         }
38 
39         cout << result << endl;
40     }
41     return 0;
42 }