ผลรวมบิโทนิก subarray สูงสุดใน C ++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมบิโตนิก subarray สูงสุดใน C++

Bitonic Subarray เป็นอาร์เรย์ย่อยพิเศษที่องค์ประกอบเพิ่มขึ้นอย่างเข้มงวดก่อนแล้วจึงลดลงหลังจากถึงจุดหนึ่งอย่างเคร่งครัด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

arr[] = {4, 2, 3, 7 ,9, 6, 3, 5, 1}

ผลลัพธ์

30

คำอธิบาย

อาร์เรย์ย่อย bitonic คือ [2, 3, 7, 9, 6, 3] ผลรวม =2 + 3 + 7 + 9 + 6 + 3 =30

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาคล้ายกับปัญหาในลำดับย่อยของบิตโทนิก เราจะสร้างสองอาร์เรย์ incSubArr[] และ decSubArr[] ที่จะสร้างร้านค้าที่เพิ่มขึ้นและลดอาร์เรย์ย่อย ที่ดัชนี i incSubArr[i] จะพบการเพิ่ม subarray จาก 0 เป็น i และ decSubArr[i] จะพบ subarray ที่เพิ่มขึ้นจาก i เป็น N

maxSum คือค่าสูงสุดที่คำนวณเป็น (incSubArr[i] + decSubArr[i] - arr[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;
}

ผลลัพธ์

The Maximum Sum of Bitonic Subarray is 30