C++ 解法, 执行用时: 12ms, 内存消耗: 924KB, 提交时间: 2022-05-02

#include<bits/stdc++.h>
using namespace std;
int n,t,sum,dpmax=INT_MIN,dpmin=INT_MAX;
int main(){
    scanf("%d",&n);
    int tmax=dpmax,tmin=dpmin;
    for(int i=1;i<=n;i++){
        scanf("%d",&t);
        sum+=t;
        tmax=max(tmax+t,t);
        tmin=min(tmin+t,t);
        dpmax=max(dpmax,tmax);
        dpmin=min(dpmin,tmin);
    }
    if(dpmax>=0&&dpmax+dpmin<sum)dpmax=sum-dpmin;
    printf("%d\n",dpmax);
    return 0;
}

C 解法, 执行用时: 13ms, 内存消耗: 684KB, 提交时间: 2022-04-02

#include<stdio.h>
int findmax(int a, int b) {
    if(a>b) return a;
    return b;
}
int findmin(int a, int b) {
    if(a<b) return a;
    return b;
}
int main() {
    int n;
    scanf("%d",&n);
    int num[n];
    for(int i=0;i<n;i++) {  
        scanf("%d",&num[i]);
    }
    int curmax=0,maxSum=num[0],curmin=0,minSum=num[0],tot=0;
    for(int i=0; i<n; i++) {
        tot += num[i];
        curmax = findmax(curmax+num[i], num[i]);
        maxSum = findmax(curmax, maxSum);
        curmin = findmin(curmin+num[i], num[i]);
        minSum = findmin(curmin, minSum);
    }
    if(maxSum < 0) {
        printf("%d",maxSum);
    }
    else {
        printf("%d",findmax(maxSum, tot - minSum));
    }
    
    return 0;
}

C++ 解法, 执行用时: 13ms, 内存消耗: 792KB, 提交时间: 2022-03-27

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int a[100000];
int main(){
    IOS;
    int n,s=0,maxs=INT_MIN,mins=INT_MAX,tmax=0,tmin=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++){
        s+=a[i];
        tmax=max(tmax+a[i],a[i]);
        tmin=min(tmin+a[i],a[i]);
        maxs=max(maxs,tmax);
        mins=min(mins,tmin);
    }
    cout<<(maxs>0?max(maxs,s-mins):maxs);
    return 0;
}

Go 解法, 执行用时: 13ms, 内存消耗: 5204KB, 提交时间: 2022-04-01

package main

import (
    "bufio"
    "os"
    "fmt"
    "strconv"
    "strings"
    "math"
)

// 1.求出[1-n]之间连续最长子序列和
// 2.如果最长序列和是包括首尾，那反之除去这部分的序列是连续最小子序列和
//   那么就找最小子序列和即可，用[1-n]序列和来减去最小子序列
// 比较1和2谁更大

func main(){
    input :=bufio.NewScanner(os.Stdin)
    buf :=make([]byte,20000*1024)
    input.Buffer(buf,len(buf))
    for input.Scan(){
        n,_ :=strconv.Atoi(input.Text())
        input.Scan()
        str := strings.Split(input.Text()," ")
        data :=make([]int,n+1)
        for i:=0;i<n;i++{
            temp,_ :=strconv.Atoi(str[i])
            data[i+1] = temp
        }
        dp := data[1]
        maxDp :=dp
        sumData :=dp
        for i:=2;i<=n;i++{
            sumData += data[i]
            // 计算当前dp
            dp = data[i] + int(math.Max(float64(dp),float64(0)))
            maxDp = int(math.Max(float64(maxDp),float64(dp)))
        }
        // 找当前序列的最短子序列和
        dp = data[1]
        minDp :=0
        for i:=2;i<n;i++{
            // 计算当前dp
            dp = data[i] + int(math.Min(float64(dp),float64(0))) // 加负数越加越小
            minDp = int(math.Min(float64(minDp),float64(dp)))
        }
        fmt.Println(int(math.Max(float64(maxDp),float64(sumData-minDp))))
    }
}

C 解法, 执行用时: 14ms, 内存消耗: 644KB, 提交时间: 2022-04-29

#include<stdio.h>

int findmax(int a, int b) {
    if(a>b) return a;
    return b;
}
int findmin(int a, int b) {
    if(a<b) return a;
    return b;
}
int main() {
    int n;
    scanf("%d",&n);
    int num[n];
    for(int i=0;i<n;i++) {  
        scanf("%d",&num[i]);
    }
    int curmax=0,maxSum=num[0],curmin=0,minSum=num[0],tot=0;
    for(int i=0; i<n; i++) {
        tot += num[i];
        curmax = findmax(curmax+num[i], num[i]);
        maxSum = findmax(curmax, maxSum);
        curmin = findmin(curmin+num[i], num[i]);
        minSum = findmin(curmin, minSum);
    }
    if(maxSum < 0) {
        printf("%d",maxSum);
    }
    else {
        printf("%d",findmax(maxSum, tot - minSum));
    }
    
    return 0;
}