动态规划求旋转寿司美味的最大值

我们先不要去管数组是环形的情况，利用动态规划求解连续子数组的最大和以及最小和。
(1) 不考虑环形得到的最大值：题中允许寿司首尾相连的环形数组情况，因此常规求得的连续子数组的最大和就是我们排除这种情况之外的所有情况中的最大和。
(2) 只考虑环形得到的最大值：而对于首尾相连的情况，我们可以这样考虑，如果常规求得的连续子数组的和达到了最小，那么总和减去这个最小值就等于首尾相连情况的最大值了。
因此最大的美味值就是(1)和(2)两种情况中大的那个。

接下来说下连续子数组的最大和：
状态定义：dp[i]为以i结尾的连续子数组的最大和
状态转移方程：dp[i] = max(dp[i-1] + array[i], array[i])
如果前边的最大和dp[i-1]为负数的话，再加上去就是负贡献，会让整体的最大和变小，因此选择从当前的美味开始累加。
在这基础上，我们还能进行降维，因为当前dp[i]只与上一个有关，因此没必要使用数组。
而连续子数组的最小和就是将上面的max改为min

import java.io.*;
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());
        for(int t = 0; t < T; t++){
            int n = Integer.parseInt(br.readLine());
            String[] values = br.readLine().trim().split(" ");
            int sum = 0;
            int[] valuess = new int[n];
            int i = 0;
            //求整体和
            for(i =0; i < n; i++){
                valuess[i] = Integer.parseInt(values[i]);
                sum += valuess[i];
            }
            int max = valuess[0];
            int min = valuess[0];
            int dp_i_max = valuess[0];
            int dp_i_min = valuess[0];
            //一起动态规划
            for(i = 1; i < n; i++){
                //每个以i结尾的连续子数组的最大值dp[i]更新
                dp_i_max = Math.max(valuess[i], dp_i_max + valuess[i]);
                //对每个连续子数组dp[i]的值取其中的最大值
                max = Math.max(max, dp_i_max);
                //同理
                dp_i_min = Math.min(valuess[i], dp_i_min + valuess[i]);
                min = Math.min(min, dp_i_min);
            }
            //考虑到是环形数组，所以拿常规的最大值 和 环形和-最小值 来做比较
            System.out.println(Math.max(max, sum - min));
        }
    }
}