C ++中的最大总和交替子序列
在本教程中，我们将讨论一个程序，以找到最大和交替子序列。
为此，我们将提供一个整数数组。我们的任务是找到一个交替子序列的最大和，即先减小，然后增大，然后减小等等的序列。
示例
#include<bits/stdc++.h>
using namespace std;
//返回最大和交替序列
int maxAlternateSum(int arr[], int n) {
if (n == 1) return arr[0];
int dec[n];
memset(dec, 0, sizeof(dec));
int inc[n];
memset(inc, 0, sizeof(inc));
dec[0] = inc[0] = arr[0];
int flag = 0 ;
for (int i=1; i<n; i++) {
for (int j=0; j<i; j++) {
if (arr[j] > arr[i]) { dec[i] = max(dec[i], inc[j]+arr[i]); flag = 1; }
else if (arr[j] < arr[i] && flag == 1) inc[i] = max(inc[i], dec[j]+arr[i]);
}
}
int result = INT_MIN;
for (int i = 0 ; i < n; i++) {
if (result < inc[i])
result = inc[i];
if (result < dec[i]) result = dec[i];
}
return result;
}
int main() {
int arr[]= {8, 2, 3, 5, 7, 9, 10};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum sum = " << maxAlternateSum(arr , n ) << endl;
return 0;
}输出结果
Maximum sum = 25