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

解法のアプローチ

この解法は、バイトニック部分列（bitonic subsequence）の問題と考え方が似ています。ここでは、incSubArr[] と decSubArr[] という2つの補助配列を作成します。それぞれ、増加方向と減少方向の部分配列の合計値を格納します。

• incSubArr[i]：インデックス 0 から i までの範囲で構成される増加部分配列の合計
• decSubArr[i]：インデックス i から N-1 までの範囲で構成される減少部分配列の合計

そして、各インデックス i において (incSubArr[i] + decSubArr[i] - arr[i]) を計算し、その最大値が答えとなります。arr[i] を引くのは、山頂となる要素が両方の配列で二重にカウントされるためです。

C++での実装例

以下は、このソリューションの動作を示すサンプルプログラムです。

#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

計算量の分析

• 時間計算量：O(N) — 配列を前方向・後ろ方向・最終集計の合計3回走査するだけで済むため、線形時間で処理できます。
• 空間計算量：O(N) — 増加用と減少用の2つの補助配列が必要になります。

まとめ

バイトニック部分配列の最大合計問題は、動的計画法（DP）の考え方を応用することで効率的に解くことができます。増加方向と減少方向それぞれの累積和を事前に計算しておき、各位置を「山頂」とみなしたときの合計を評価する、というシンプルな発想がポイントです。競技プログラミングや配列操作の練習としても非常に良い題材なので、ぜひ自分でも実装してみてください。