Trong bài toán này, chúng ta được cung cấp một mảng arr []. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng số tối đa của dãy con Bi-tonic trong C ++.
Thuốc bổ sinh học dãy con là một dãy đặc biệt có các phần tử đầu tiên tăng và sau đó giảm.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1} Đầu ra
33
Giải thích
Dãy số Bi-tonic cho tổng lớn nhất là {2, 3, 7, 9, 6, 5, 1} Sum =2 + 3 + 7 + 9 + 6 + 5 + 1 =33
Phương pháp tiếp cận giải pháp
Để tìm dãy con bitonic có tổng lớn nhất, chúng ta sẽ tạo hai mảng, incSeq [] và decSeq [] theo cách sao cho một phần tử i ở chỉ mục, incSeq [i] có tổng tất cả các phần tử từ arr [0… i] đúng tăng và decSeq [i] có tổng tất cả các phần tử từ arr [i… n] đang giảm dần.
Cuối cùng, chúng tôi sẽ trả về maxSum là giá trị lớn nhất từ (incSeq [i] + decSeq [i] - arr [i]).
Ví dụ
Chương trình minh họa từ ngữ của giải pháp của chúng tôi,
#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxSumBiTonicSubSeq(int arr[], int N){
int maxSum = -1;
int incSeq[N], decSeq[N];
for (int i = 0; i < N; i++){
decSeq[i] = arr[i];
incSeq[i] = arr[i];
}
for (int i = 1; i < N; i++)
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && incSeq[i] < incSeq[j] + arr[i]) incSeq[i] = incSeq[j] + arr[i];
for (int i = N - 2; i >= 0; i--)
for (int j = N - 1; j > i; j--)
if (arr[i] > arr[j] && decSeq[i] < decSeq[j] + arr[i])
decSeq[i] = decSeq[j] + arr[i];
for (int i = 0; i < N; i++)
maxSum = calcMaxVal(maxSum, (decSeq[i] + incSeq[i] - arr[i]));
return maxSum;
}
int main(){
int arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1};
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The Maximum Sum of Bi-tonic subsequence is : "<<findMaxSumBiTonicSubSeq(arr, N);
return 0;
} Đầu ra
The Maximum Sum of Bi-tonic subsequence is : 33