首页 > 试题广场 >

回转寿司

[编程题]回转寿司

热度指数：8554 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美请小团吃回转寿司。转盘上有N盘寿司围成一圈，第1盘与第2盘相邻，第2盘与第3盘相邻，…，第N-1盘与第N盘相邻，第N盘与第1盘相邻。小团认为第i盘寿司的美味值为A[i]（可能是负值，如果小团讨厌这盘寿司）。现在，小团要在转盘上选出连续的若干盘寿司，使得这些寿司的美味值之和最大（允许不选任何寿司，此时美味值总和为0）。

输入描述:

第一行输入一个整数T（1<=T<=10），表示数据组数。
每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；
第二行输入N个由空格隔开的整数，表示A[1]到A[N]（-10^4<=A[i]<=10^4）。

输出描述:

每组数据输出占一行，输出一个整数，表示连续若干盘寿司的美味值之和的最大值。

示例1

输入

1
4
3 -2 4 -1

输出

说明

美味值之和最大连续若干盘寿司为第3盘、第4盘和第1盘。

算法知识视频讲解

Java

呆牛一头

我来一个java版的单调队列+前缀和+窗口滑动：借用上面的思路：sum[j]-min(sum[i])得到最大窗口值，min(sum[i])通过单调栈来维护，同时需要维护窗口宽度

package main;

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;


public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int T=Integer.parseInt(br.readLine().trim());
        for(int i=0;i<T;i++){
            int N=Integer.parseInt(br.readLine().trim());
            String[] str=br.readLine().trim().split(" ");
            int[] A=new int[N];
            for(int j=0;j<N;j++){
                A[j]=Integer.parseInt(str[j]);
            }
            int[] nums=new int[2*N];//拼接数组，将环展开
            System.arraycopy(A,0,nums,0,A.length);
            System.arraycopy(A,0,nums,A.length,N);
            int[] sum=new int[2*N+1];
            for(int j=1;j<=2*N;j++){//前缀和
                sum[j]=sum[j-1]+nums[j-1];
            }
            int ans=Integer.MIN_VALUE;
            Deque<Integer> deque=new LinkedList<>();
            //维护一个单调栈，里面存最小的前缀和
            for(int right=0;right<=nums.length;right++){
                while(!deque.isEmpty()&&sum[deque.peekLast()]>=sum[right]){
                    deque.removeLast();
                }
                deque.addLast(right);
                int widgth=right-deque.peekFirst();//维护窗口宽度
                if(widgth>N){
                    deque.removeFirst();
                }
                ans=Math.max(ans,sum[right]-sum[deque.peekFirst()]);
            }
            bw.write(String.valueOf(ans));
            bw.newLine();
            bw.flush();
        }
        bw.close();
        br.close();
    }
}

发表于 2022-08-11 22:33:58 回复(0)

Java

牛客479854335号

//跟着楼上大神思路学的
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));

        }
    }
}

发表于 2021-08-08 18:37:57 回复(0)

Java

抗麻袋的少年

//dp......dp......dp

import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String[] args)throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String totalstr = reader.readLine();
        String str = null;
        while((str = reader.readLine())!=null){
            String s = reader.readLine();
            String[] arraystr =  s.split(" ");
            int[] array = new int[arraystr.length];
            for(int i=0;i<array.length;i++){
                array[i] = Integer.valueOf(arraystr[i]);
            }
            int total = arraystr.length;
            int[] maxvalue = new int[total];
            int[] minvalue = new int[total];
            int max = array[0];
            int min = array[0];
            maxvalue[0] = array[0];
            minvalue[0] = array[0];
            int num = array[0];
            for(int i=1;i<total;i++){
                maxvalue[i] = Math.max(array[i],array[i]+maxvalue[i-1]);
                minvalue[i] = Math.min(array[i],array[i]+minvalue[i-1]);
                max = Math.max(max,maxvalue[i]);
                min = Math.min(min,minvalue[i]);
                num = num+array[i];
            }
            System.out.println(Math.max(max,num-min));
        }
    }
}

发表于 2021-03-17 15:02:41 回复(0)