Mảng con bitonic tổng tối đa trong C ++

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 ta là tạo một chương trình để tìm mảng con bitonic có tổng tối đa trong C ++.

Bitonic Subarray là một mảng con đặc biệt, trong đó phần tử tăng nghiêm ngặt đầu tiên và sau đó giảm nghiêm ngặt sau khi đạt đến một điểm nhất định.

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

30

Giải thích

Mảng con bitonic là [2, 3, 7, 9, 6, 3] .Sum =2 + 3 + 7 + 9 + 6 + 3 =30

Phương pháp tiếp cận giải pháp

Giải pháp tương tự như trong bài toán con bitonic. Chúng ta sẽ tạo hai mảng incSubArr [] và decSubArr []. Điều đó sẽ tạo ra các phân tầng con tăng và giảm cửa hàng. Tại chỉ mục i, incSubArr [i] sẽ tìm thấy mảng con tăng dần từ 0 đến i. Và decSubArr [i] sẽ tìm thấy các mảng con ngày càng tăng từ i đến N.

Giá trị maxSum là giá trị lớn nhất được tính bằng (incSubArr [i] + decSubArr [i] - arr [i]).

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>
using namespace std;
int findMaxSumBiTonicSubArr(int arr[], int N){
   int incSubArr[N], decSubArr[N];
   int max_sum = -1;
   incSubArr[0] = arr[0];
   for (int i=1; i<N; i++)
      if (arr[i] > arr[i-1])
         incSubArr[i] = incSubArr[i-1] + arr[i];
      else
         incSubArr[i] = arr[i];
   decSubArr[N-1] = arr[N-1];
   for (int i= (N-2); i>=0; i--)
      if (arr[i] > arr[i+1])
         decSubArr[i] = decSubArr[i+1] + arr[i];
      else
         decSubArr[i] = arr[i];
   for (int i=0; i<N; i++)
      if(max_sum < (incSubArr[i] + decSubArr[i] - arr[i]))
max_sum = incSubArr[i] + decSubArr[i] - arr[i];
   return max_sum;
}
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 Bitonic Subarray is "<<findMaxSumBiTonicSubArr(arr, N);
   return 0;
}

Đầu ra

The Maximum Sum of Bitonic Subarray is 30