签入签出

ACWing.1478 👈题目链接👉 PAT.1006

每天第一个到机房的人负责开门，最后一个从机房离开的人负责锁门。
现在，给定每个人的签到与签出记录，请你找出当天开门的人以及锁门的人分别是谁。

#include<iostream>
using namespace std;
const int N = 110;
int n;
int main(){
    cin>>n;
    string ear="24:59:59",las,ear_id,las_id;
    while(n--){
        string id,st,ed;
        cin>>id>>st>>ed;
        if (st<ear) ear = st, ear_id = id;
        if (ed>las) las = ed, las_id = id;
    }
    cout<<ear_id<<" "<<las_id;
}

最大子段和

ACWing.1479 👈题目链接👉 PAT.1007

输出最大子段和以及起始与结束位置的元素;

只输出最大子段和的代码很简单，状态表示是一维

int main(){
    cin>>n;
    for (int i = 1;i<=n;i++) cin>>w[i];
    int res,l,r;
    for (int i = 1,f=-1;i<=n;i++) 
    {
        f = max(0,f);
        f = f + w[i];
        res = max(res,f);
    }
    cout<<res;
}

输出开始与结束位置，需要考虑两次更新的地方，插入记录的代码；
这里有一点重要的性质是：局部最大子段是相互不重叠的。

#include<iostream>
using namespace std;
const int N = 10010;
int n;
int w[N];

int main(){
    cin>>n;
    for (int i = 1;i<=n;i++) cin>>w[i];
    int res=-1,l,r;
    for (int i = 1,f=-1,st = 1;i<=n;i++) 
    {
        if (f<0) st = i, f=0;
        f = f + w[i];
        if (f>res) //触发结果更新
        {
            l = w[st];
            r = w[i];
            res = f;
        }
    }
    if (res<0) res=0, l=w[1], r=w[n];
    cout<<res<<" "<<l<<" "<<r;
}