在本教程中,我们将讨论一个程序,以找到最大和交替子序列。
为此,我们将提供一个整数数组。我们的任务是找到一个交替子序列的最大和,即先减小,然后增大,然后减小等等的序列。
#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