在线规划算法解决最大子数列和问题

在线规划算法作为我所接触的第一个高级算法，其效率高，核心价值在于"在有限的时间内生成足够好的决策"而非追求全局最优，具有动态适应性。

代码实现

#include <iostream>
using namespace std;
            
int main() {
    std::ios::sync_with_stdio(false);
    int n, begin = 0, end = 0, temp_begin = 0;
    long long sum = 0;
    int temp = 0;
    cin >> n;
    int *p = new int[n]; 
    for(int i = 0; i < n; i++) {
        cin >> p[i];
    }
    long long max = -1;
    for(int i = 0; i < n; i++) {
        sum += p[i];
        if(sum > max) {
            end = i;
            max = sum;
            begin = temp_begin;
        }
        if(sum < 0) {
            sum = 0;
            temp_begin = i + 1;// 重置时设置下一个位置为起点
        }
    }
        if(max < 0) {
            max = 0;
            begin = 0;
            end = n-1;
        }
        cout << max << " " << p[begin] << " " << p[end];
        delete[] p;
        return 0;
}