回转寿司

#include <bits/stdc++.h>
using namespace std;
int main(){
    int T,N;
    cin>>T;
    for(int i=0;i<T;i++){
        cin>>N;
        int Max=INT_MIN,Min=INT_MAX,res;
        vector<int> arr(N);
        for(int i=0;i<N;i++){
            cin>>arr[i];
        }
        int total=0;
        vector<int>dpMax(N);
        vector<int>dpMin(N);
        dpMax[0]=dpMin[0]=arr[0];
        total+=arr[0];
        //分析，最大值为单个序列最大或是首尾相连(总和减去最小值),取两者最大
        for(int i=1;i<N;i++){
            total+=arr[i];
            dpMax[i]=max(dpMax[i-1]+arr[i],arr[i]);
            dpMin[i]=min(dpMin[i-1]+arr[i],arr[i]);
            if(Max<dpMax[i]) Max=dpMax[i];
            if(Min>dpMin[i]) Min=dpMin[i];
        }
        res = max(Max,total-Min);
        cout<<res<<endl;
    }
        return 0;
}

res = max(Max,total-Min);

def findMaxSum(N,score):
    '''
    动态规划的想法：
    pre[i]储存以第i个数结尾的连续数组的最大和，这样的连续数组只有两种可能
    第一种，这个数组只有一个数，即第i个数
    第二种，这个数组多于一个数，那么就是第i个数加以第i-1个数结尾的连续数组的最大和pre[i-1]
    取这两个值的最大值
    '''
    pre = [0]
    for i in range(N):
        maxSum = max(score[i],score[i]+pre[i])
        pre.append(maxSum)
    return max(pre)


T = int(input())
while T:
    T = T-1
    N = int(input())
    score = list(map(int, input().split()))
    maximum = findMaxSum(N,score)
    minimum = findMaxSum(N,[-i for i in score])
    if sum(score)+minimum>maximum:
        maximum = sum(score)+minimum
    print(maximum)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            String[] strArr = br.readLine().trim().split(" ");
            int[] yummy = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
                yummy[i] = Integer.parseInt(strArr[i]);
                sum += yummy[i];
            }
            int m1=0,m2=0;
            int res1=Integer.MIN_VALUE;
            int res2=Integer.MAX_VALUE;
            // res1  无环情况下的最大值
            for(int i=0;i<yummy.length;i++){
                m1+=yummy[i];
                res1=Math.max(m1,res1);
                if(m1<0){
                    m1=0;
                }
            }
            //res2   无环情况下的最小值  数组的总和减去无环情况下的最小值就是有环情况下的最大值
            for(int i=0;i<yummy.length;i++){
                m2+=yummy[i];
                res2=Math.min(m2,res2);
                if(m2>0){
                    m2=0;
                }
            }
            System.out.println(Math.max(res1,sum-res2));
        }
    }
}

//跟着楼上大神思路学的
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String s = input.nextLine().trim();
        int m = Integer.parseInt(s);//共有m组数据
        for(int i = 0;i < m;i++){

            int n = Integer.parseInt(input.nextLine().trim());//有n个寿司

            int[] A = new int[n];//存放寿司美味值
            int totalSum = 0;//寿司美味值总和

            String[] s1 = input.nextLine().split(" ");
            for(int j = 0;j < n;j++){
                A[j] = Integer.parseInt(s1[j]);//接收美味值数据
                totalSum += A[j];//计算美味值总和
            }

            int resSum = Integer.MIN_VALUE;//存放最终结果-环形子数组最大和
            int maxSum = Integer.MIN_VALUE;//存放无环情况下，A[]数组的最大累加和
            int minSum = Integer.MAX_VALUE;//存放无环情况下，A[]数组的最小累加和
            int[] dpMaxSum = new int[n];//当遇到下一个A[i]为正的时候，贡献度为正，那么就继续累加，贡献度为负，那么就从A[i]重现计算贡献度
            int[] dpMinSum = new int[n];//
            dpMaxSum[0] = A[0];
            dpMinSum[0] = A[0];

            for(int j = 1;j < n;j++){
                dpMaxSum[j] = Math.max(dpMaxSum[j - 1] + A[j],A[j]);
                dpMinSum[j] = Math.min(dpMinSum[j - 1] + A[j],A[j]);
                maxSum = Math.max(dpMaxSum[j],maxSum);
                minSum = Math.min(dpMinSum[j],minSum);
            }
            /*这里这样理解->分两种情况:
           情况一：A数组首尾元素没有同时在最大累加和的子数组中，对应这里的maxSum
            情况二：A数组收尾元素同时在最大累加和的子数组中，因而最小累加和子数组
                便对应的是无环的情况，所以用A数组元素总和减去无环最小累加和即为所得

             */
            System.out.println(Math.max(totalSum - minSum,maxSum));

        }
    }
}

import sys

T = int(sys.stdin.readline().strip('\n'))
for i in range(T):
    N = int(sys.stdin.readline().strip('\n'))
    l = [int(x) for x in sys.stdin.readline().strip('\n').split()]
    r_min = l.copy()
    r_max = l.copy()
    for i in range(1, len(l)):
        r_min[i] = min(r_min[i],r_min[i-1]+r_min[i]) #找到非环形最小和
        r_max[i] = max(r_max[i], r_max[i - 1] + r_max[i]) #非环形最大和
    print(max(sum(l)-min(r_min),max(r_max))) # max(total-非环形最小和，非环形最大和）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        vector<int> nums(n, 0);
        for (int i = 0; i < n; ++i)
            cin >> nums[i];
        int dp[n][2];
        dp[0][0] = nums[0] >= 0? nums[0] : 0;
        dp[0][1] = nums[0] <= 0? nums[0] : 0;
        int max_value = dp[0][0], min_value = dp[0][1], sum = nums[0];
        for (int i = 1; i < n; ++i)
        {   
            sum += nums[i];
            dp[i][0] = max(dp[i - 1][0] + nums[i], nums[i]);
            max_value = max(max_value, dp[i][0]);
            dp[i][1] = min(dp[i - 1][1] + nums[i], nums[i]);
            min_value = min(min_value, dp[i][1]);
        }
        cout << max(max_value, sum - min_value) << endl;
    }
}

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

int T,N;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>T){
        while(cin >> N){
            vector<int> sushi(N);
            for(int i = 0;i < N;i++){
                cin>>sushi[i];
            }
            int res = INT_MIN;
            //分别统计0-N和超过N的情况，超过N的情况就是求内部最小值，用数组和减去它即可
            int nio = 0, min_nio = INT_MAX,max_nio = INT_MIN, min_inter = INT_MAX;
            for(int i = 0;i < N;i++){
                nio += sushi[i%N];
                min_nio = min(min_nio, nio);
                max_nio = max(max_nio, nio);
                min_inter = min(min_inter, nio - max_nio);
                res = max(res, nio - min_nio);
            }
            //由边界向内部    
            
            printf("%d\n",max(res, nio- min_inter));
        }
    }
}

import sys

n=int(input())
for _ in range(n):
    N=int(input())
    A=list(map(int,sys.stdin.readline().strip().split()))
    s=sum(A)
    sum1=0
    sum2=0
    ans=0
    for num in A:
        if sum1>=0:
            sum1+=num
        else:
            sum1=num
        if sum2<=0:
            sum2+=num
        else:
            sum2=num
        ans=max(ans,sum1)
        ans=max(ans,s-sum2)
    print(ans)

//1 设想最大连续队列不跨环 那么就是常规求动态规划问题 可得一个最大连续值
//2.设想最大连续队列跨环，那么就是求最小连续不跨环和问题(跨环最大值=数组总和-最小不跨环总和) 可得一个最大值
//3.比较它们俩的最大值，返回，总共2种情况，属于分类讨论了

package 美团2021校招第9场.回转寿司;  import java.util.Scanner;  public class Main { public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);  int groups = scanner.nextInt();  for (int i = 0; i < groups; i++) { int n = scanner.nextInt();  int[] nums = new int[n];  for (int j = 0; j < n; j++) {
                nums[j] = scanner.nextInt();  }
            System.out.println(solution(nums,n));  }
    } public static int solution(int[] nums,int n){ int[] dpWithLoop = new int[n];  int[] dpWithOutLoop = new int[n];  int sum = 0;  for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];  } int maxWithLoop = 0;  int maxWithOutLoop = 0;  dpWithOutLoop[0] = nums[0];  dpWithLoop[0] = nums[0];  if(dpWithOutLoop[0]>maxWithOutLoop){
            maxWithOutLoop = dpWithOutLoop[0];  } if(sum-dpWithLoop[0]>maxWithLoop){
            maxWithLoop = sum-dpWithLoop[0];  } for (int i = 1; i < nums.length; i++) {
            dpWithOutLoop[i] = Math.max(nums[i],nums[i]+dpWithOutLoop[i-1]);  if(dpWithOutLoop[i]>maxWithOutLoop){
                maxWithOutLoop = dpWithOutLoop[i];  }
        } for (int i = 1; i < nums.length; i++) {
            dpWithLoop[i] = Math.min(nums[i],nums[i]+dpWithLoop[i-1]);  if(sum-dpWithLoop[i]>maxWithLoop){
                maxWithLoop = sum-dpWithLoop[i];  }
        } return Math.max(maxWithLoop,maxWithOutLoop);  }
}

//第一个回答的思路+贪心
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        int len,sum_min=0,sum_max=0,sum=0,min=1000,max=-1000;
        cin>>len;
        while(len--){
            int tmp;
            cin>>tmp;
            sum+=tmp;
            sum_max+=tmp;
            sum_min+=tmp;
            max=max>sum_max?max:sum_max;
            min=min<sum_min?min:sum_min;
            if(sum_max<0)
                sum_max=0;
            if(sum_min>0)
                sum_min=0;
        }
        int bigger=max>sum-min?max:sum-min;
        cout<<bigger<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        int ans = 0;
        cin >> n;
        vector<int>v(n), lrdp(n, INT_MIN), rldp(n, INT_MIN), lr(n, 0), rl(n, 0), lrmax(n, 0), rlmax(n+1, 0);
         
        for(int i = 0; i < n; i++) {
            cin >> v[i];
            lr[i] = i == 0? v[i]: v[i] + lr[i-1];
            lrmax[i] = i == 0 ? max(0, lr[i]) : max(lrmax[i-1], lr[i]);
        }
        for (int i = n - 1; i >= 0; --i) {
            rl[i] = i == n-1 ? v[i] : v[i] + rl[i + 1];
            rlmax[i] = i == n-1 ? max(0, rl[i]) : max(rlmax[i + 1], rl[i]);
        }
        lrdp[0] = v[0];
        ans = max(lrdp[0], ans);
        for(int i = 1; i < n; ++i) {
            lrdp[i] = lrdp[i-1] > 0 ? lrdp[i-1] + v[i]: v[i];
            ans = max(ans, lrdp[i]);
        }
        rldp[n-1] = v[n-1];
        ans = max(ans, rldp[n-1]);
        for(int i = n-2; i >= 0; i--) {
            rldp[i] = rldp[i+1] > 0 ? rldp[i+1] + v[i]: v[i];
            ans = max(rldp[i], ans);
        }
        for (int i = 0; i < n; i++) {
            ans = max(ans, lrmax[i] + rlmax[i+1]);
        }
         
        cout << ans << endl;
         
    }
}

1. 破环成链, 计算链上所有长度小于等于N的区间的最大值即可
2. 使用前缀和技巧计算区间和, 对于i位置, 需要计算以i位置为末尾的
   最大子区间和的话, 只需找到前缀和最小的j位置, s[i] - s[j]即为所求
3. 枚举每个位置, 对于当前位置, 可行前缀在一个长度为N的滑动窗口内部
4. 使用单调队列求滑动窗口内的最小值

整体算法的时间复杂度 O(N) 
(如果使用优先队列实现查找滑动窗口内的前缀最小值则时间复杂度为 O(NlogN))
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int w[N], s[N];


void solve(){
    deque<int> dq;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> w[i];
        w[i + n] = w[i];
    }
    for (int i = 1; i <= 2 * n; i ++ )
        s[i] = s[i - 1] + w[i];
    dq.push_front(0);
    int ans = 0;

    for (int i = 1; i <= 2 * n; i ++ ) {
        if (i >= dq.front() + n)
            dq.pop_front();
        if (dq.size()) {
            ans = max(ans, s[i] - s[dq.front()]);
            // cout << i << ' ' << s[i] << ' ' << ans << ' ' << dq.front() << ' ' << s[dq.front()] << endl;
        }
        while (dq.size() and s[dq.back()] > s[i])
            dq.pop_back();
        dq.push_back(i);
    }
    cout << ans << endl;    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

T = int(input())
while T>0:
    N = int(input())
    food = list(map(int,input().split()))
    dp = [0]*N
    dp[0] = food[0]
    for i in range(1,N):
        dp[i] = max(dp[i-1]+food[i],food[i])
    res_one = max(dp)
    summry = sum(food)
    dp_new = [0]*N
    dp_new[0] = food[0]
    for i in range(1,N):
        dp_new[i] = min(dp_new[i-1]+food[i],food[i])
    res_two = summry - min(dp_new)
    print(max(res_one,res_two))
    T-=1

def solve(N,l):
    p=[0]
    for i in range(N):
        p.append(max(l[i],l[i]+p[i]))
    return max(p)
T=int(input())
while T:
    T-=1
    n=int(input())
    l=[int(i) for i in input().split()]
    a=solve(n,l)
    b=solve(n,[-i for i in l])
    c=max(sum(l)+b,a)
    print(c)