Trong bài toán này, chúng ta cho một mảng arr [] gồm n số nguyên. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tổng lớn nhất xen kẽ dãy con bắt đầu từ phần tử đầu tiên của mảng.
Một dãy con xen kẽ là một dãy con trong đó các phần tử đang tăng và giảm theo một thứ tự xen kẽ, tức là đầu tiên giảm, sau đó tăng dần, sau đó giảm dần. Ở đây, dãy con xen kẽ ngược lại không hợp lệ để tìm tổng lớn nhất.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {5, 1, 6, 2, 4, 8, 9} Đầu ra
27
Giải thích
Starting element: 5, decrease: 1, increase: 6, decrease: 2, increase:4, N.A. Here, we can use 4, 8, 9 as the last element of the subsequence. Sum = 5 + 1 + 6 + 2 + 4 + 9 = 27
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp lập trình động, vì vậy chúng tôi sẽ sử dụng hai mảng một để lưu trữ tổng các nguyên tố tối đa kết thúc bằng arr [i], trong đó arr [i] đang tăng lên. Khác để lưu trữ chúng tổng số tối đa của các phần tử kết thúc bằng arr [i], trong đó arr [i] đang giảm dần.
Sau đó, chúng tôi sẽ thêm từng phần tử bằng cách kiểm tra xem chúng có phải là chuỗi thay thế hay không. Đối với mỗi mảng, chúng tôi sẽ tính tổng lớn nhất cho đến chỉ mục. Và trả về giá trị lớn nhất sau khi duyệt qua n phần tử.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include<iostream>
#include<cstring>
using namespace std;
int maxVal(int x, int y){
if(x > y)
return x;
return y;
}
int calcMaxSumAltSubSeq(int arr[], int n) {
int maxSum = −10000;
int maxSumDec[n];
bool isInc = false;
memset(maxSumDec, 0, sizeof(maxSumDec));
int maxSumInc[n];
memset(maxSumInc, 0, sizeof(maxSumInc));
maxSumDec[0] = maxSumInc[0] = arr[0];
for (int i=1; i<n; i++) {
for (int j=0; j<i; j++) {
if (arr[j] > arr[i]) {
maxSumDec[i] = maxVal(maxSumDec[i],
maxSumInc[j]+arr[i]);
isInc = true;
}
else if (arr[j] < arr[i] && isInc)
maxSumInc[i] = maxVal(maxSumInc[i],
maxSumDec[j]+arr[i]);
}
}
for (int i = 0 ; i < n; i++)
maxSum = maxVal(maxSum, maxVal(maxSumInc[i],
maxSumDec[i]));
return maxSum;
}
int main() {
int arr[]= {8, 2, 3, 5, 7, 9, 10};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum sum alternating subsequence starting is "<<calcMaxSumAltSubSeq(arr , n);
return 0;
} Đầu ra
The maximum sum alternating subsequence starting is 25