最大子段和的表

dp[i] 表示以第 i 个数结尾的最大连续和。

运行下面这段程序：

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> max_sub_tab(const vector<int>& a) {
    vector<int> dp(a.size());
    dp[0] = a[0];
    for (size_t i = 1; i < a.size(); i++) dp[i] = max(a[i], dp[i - 1] + a[i]);
    return dp;
}

template <class T>
string join(const vector<T>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + to_string(v[i]);
    return s;
}

int main() {
    cout << join(max_sub_tab({-2, 1, -3, 4, -1, 2, 1, -5, 4})) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）