题解 | #环形数组的连续子数组最大和#java小白

本题用动态规划求解

本题难点在于这个数组是一个环，第一个元素的前一个元素时最后一个元素，不然就是简单的求最大和的连续子序列
状态转移方程为：
dp[i] = max(dp[i]+ints[i],ints[i])
dp为以第i个元素结尾的子序列的最大和

而求最大和，最大和有两种情况，包含首尾以及不包含
分清楚情况，然后计算就是算出两种情况的大小，相比返回最大值即可
当已知一种情况的最大值时，另一种的最大值即为总和减去最小值，因为最大最小两个子序列是连续的，试想一下，如果一段连续的序列大于零，那就自动归于最大值序列了，那小于零呢？
所以总的减去最小的即为相反情况

特殊情况：当数组全零或者全为负数时，直接返回最大值即可

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(
                new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int ans = Integer.MIN_VALUE;
        int length = 0;
        st.nextToken();
        length = (int) st.nval;
        if (length == 1){
            st.nextToken();
            ans = (int) st.nval;
            pw.println(ans);
            pw.flush();
            return;
        }
        int[] ints = new int[length];
        for (int i = 0; i < length; i++) {
            st.nextToken();
            ints[i] = (int) st.nval;
        }

        int sum = ints[0];//和
        int dpMax = ints[0];//dp
        int tempMax = ints[0];//最大值
        int dpMin = ints[0];
        int tempMin = ints[0];
        for (int i = 1; i < length; i++) {
          sum += ints[i];
          dpMax = Math.max(dpMax+ints[i],ints[i]);
          tempMax = Math.max(tempMax,dpMax);
          dpMin = Math.min(dpMin+ints[i],ints[i]);
          tempMin = Math.min(tempMin,dpMin);
        }

        if (tempMax <= 0){
            ans = tempMax;

        }else {
            ans = Math.max(tempMax,sum-tempMin);
        }
        

        pw.println(ans);
        pw.flush();
    }
}