ผลรวมสูงสุดของเซิร์บอาร์เรย์ไบโทนิกใน C++

ปัญหา

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

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

ตัวอย่าง

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

อินพุต

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

เอาต์พุต

30

คำอธิบาย

เซิร์บอาร์เรย์ไบโทนิกคือ [2, 3, 7, 9, 6, 3] ผลรวม = 2 + 3 + 7 + 9 + 6 + 3 = 30

วิธีแก้ปัญหา

วิธีแก้ปัญหานี้คล้ายกับปัญหาเซิร์บซีเควลไบโทนิก เราจะสร้างอาร์เรย์สองอันคือ incSubArr[] และ decSubArr[] ที่จะเก็บเซิร์บอาร์เรย์ที่เพิ่มและลด ที่ดัชนี i incSubArr[i] จะหาเซิร์บอาร์เรย์ที่เพิ่มจาก 0 ถึง i และ decSubArr[i] จะหาเซิร์บอาร์เรย์ที่เพิ่มจาก 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 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

เอาต์พุต
The Maximum Sum of Bitonic Subarray is 30