单向量解法

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

struct ve{
    vector<int>s;
};

int main(){
    int n,tmp;
    cin >> n;
    ve nums[n];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<i+1;j++){
            cin >> tmp;
            nums[i].s.push_back(tmp);//存入数字
        }
    }
    for(int i = n-2;i>=0;i--){
        //cout<<i<<endl;
        for(int j = 0;j<i+1;j++){
            //cout<<nums[i].s[j]<<' '<<nums[i+1].s[j]<<' '<<nums[i+1].s[j+1]<<endl;
            nums[i].s[j] += max(nums[i+1].s[j],nums[i+1].s[j+1]); //  求出最大和
        }
    }
    cout<<nums[0].s[0]<<endl;
    int q,l=0,r=0;
    q = 0;
    while(q<n-1){//根据数据的数量关系推导原始数据
        if(nums[l+1].s[r]>nums[l+1].s[r+1]){
            cout<<nums[l].s[r]-nums[l+1].s[r]<<' ';
            l+=1;    
        }else{
            cout<<nums[l].s[r]-nums[l+1].s[r+1]<<' ';
            l+=1;
            r+=1;
        }
        //cout<<num1[l].s[r]<<' ';
        q++;
    }
    cout<<nums[l].s[r]<<' ';
}