Suppose that \(x\) people is initially on the bus.

After the \(i\)-th bus stop, \(x + \displaystyle\sum_{k = 1}^{i} A_k\) people are on the bus.

Considering the conditions, the answer to the problem is the minimum \(x + \displaystyle\sum_{k = 1}^{N} A_k\) subject to \(x + \displaystyle\sum_{k = 1}^{i} A_k \geq 0\) for all \(0 \leq i \leq N\). (If \(i = 0\), we assume that \(\displaystyle\sum_{k = 1}^{i} A_k = 0\).)

That \(x + \displaystyle\sum_{k = 1}^{i} A_k \geq 0\) holds for all \(0 \leq i \leq N\) if and only if \(\min(x + \displaystyle\sum_{k = 1}^{i} A_k) \geq 0\). Since \(\min(x + \displaystyle\sum_{k = 1}^{i} A_k) = x + \min(\displaystyle\sum_{k = 1}^{i} A_k)\), it is sufficient to minimize \(x + \displaystyle\sum_{k = 1}^{N} A_k\) subject to \(x + m \geq 0\), where \(m \coloneqq \min(\displaystyle\sum_{k = 1}^{i} A_k)\).

Apparently, it is optimal to take \(x = -m\). The value \(m\) can be computed in a linear time in manner of cumulative sum.

Sample code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (ll &e : a) cin >> e;
    ll m = 0, sum = 0;
    for (ll e : a) sum += e, m = min(m, sum);
    cout << sum - m << '\n';
}