C++で道路を横断するために必要な最小限の初期エネルギーを求めるアルゴリズム

正の数と負の数が格納された配列を考えてみましょう。この配列は、道路の一方の端からもう一方の端までにあるチェックポイント（中間地点）を表しています。正の値はその地点でエネルギーが増えることを、負の値はエネルギーが減ることを意味します。ここでの課題は、移動中にエネルギーレベルが決して0以下にならないようにするために、出発時に最低どれだけのエネルギーを持っていればよいのか（最小初期エネルギー）を求めることです。

例として、配列 A = {4, -6, 2, 3} の場合を考えてみます。初期エネルギーを0として出発すると、最初のチェックポイントに到達した時点でエネルギーは4になります。しかし、次のチェックポイントへ進むと 4 + (-6) = -2 となり、エネルギーが0を下回ってしまいます。そこで初期エネルギーを3にして出発すると、最初のチェックポイント通過後は 3 + 4 = 7、続くチェックポイント通過後は 7 + (-6) = 1 となり、常にエネルギーを正の値に保つことができます。

アルゴリズム

minInitEnergy(arr, n):
begin
    initEnergy := 0
    currEnergy := 0
    flag := false
    for i in range 0 to n, do
        currEnergy := currEnergy + arr[i]
        if currEnergy <= 0, then
            initEnergy := initEnergy + absolute value of currEnergy + 1
            currEnergy := 1
            flag := true
        end if
    done
    if flag is false, return 1, otherwise return initEnergy
end

このアルゴリズムでは、現在のエネルギー（currEnergy）をチェックポイントごとに累積していき、途中で0以下になった場合には、不足分を補うのに必要なエネルギーを初期エネルギー（initEnergy）に加算します。最後に、一度も補正が必要なかった場合は1を返し、補正が行われた場合は計算済みのinitEnergyを返します。

C++による実装例

#include <iostream>
#include <cmath>
using namespace std;
int minInitEnergy(int arr[], int n){
    int initEnergy = 0;
    int currEnergy = 0;
    bool flag = false;
    for (int i = 0; i<n; i++){
        currEnergy = currEnergy + arr[i];
        if (currEnergy <= 0){
            initEnergy = initEnergy + abs(currEnergy) + 1;
            currEnergy = 1;
            flag = true;
        }
    }
    if (flag == false)
        return 1;
    else
        return initEnergy;
}
int main() {
    int A[] = {4, -6, 2, 3};
    int n = sizeof(A)/sizeof(A[0]);
    cout << "Minimum Energy: " << minInitEnergy(A, n);
}

実行結果

Minimum Energy: 3