面试题：连续子数组的最大和与循环列表中的子数组最大和

一：连续子数组的最大和

LeetCode 53 Maximum Subarray

题意：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
定义dp[i]为前i个数中的连续子数组的最大和。
状态转移方程为：
d[i] = d[i-1]>=0 ? d[i-1]+nums[i] : nums[i]

		if not nums: return 0
        dp = [0]*len(nums)
        
        dp[0] = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1]+nums[i], nums[i]) # dp[i] means the maximum subarray ending with A[i]
            res = max(res, dp[i])
        return res

优化空间复杂度：

public static int get(int[] array) {
    int max = 0,temp = 0;
    for (int i = 0; i < array.length; i++) {
        temp += array[i];
        if (temp < 0)
            temp = 0;
        if (max < temp)
            max = temp;
    }
    return max;
}

二：循环列表中的子数组最大和

参考博客：https://blog.csdn.net/weixin_43320847/article/details/83045856
这个问题的解可以分为两种情况：

• 最大子数组没有跨越 array[n-1] 到 array[0] （原问题）
• 最大子数组跨越 array[n-1] 到 array[0]

对于第二种情况，我们不妨换个思路，如果最大子序列跨越了 array[n-1] 到 array[0]，那么最小子序列肯定不会出现跨越 array[n-1] 到 array[0] 的情况。
所以，在允许数组跨界（首尾相邻）时，最大子数组的和为下面的最大值
max = { 原问题的最大子数组和，数组所有元素总值 - 最小子数组和 }

public class MaxSequence {
    
    public static int getMax(int[] array) {
        int max = 0,temp = 0;
        for (int i = 0; i < array.length; i++) {
            temp += array[i];
            if (temp < 0)
                temp = 0;
            if ( max < temp)
                max = temp;
        }
        return max;
    }

    public static int getMin(int[] array) {
        int min = 0, temp = 0;
        for (int i = 0; i < array.length; i++) {
            temp += array[i];
            if (temp > 0)
                temp = 0;
            if (temp < min)
                min = temp;
        }
        return min;
    }

    public static int getLoopMax(int[] array) {
        int max1 = getMax(array);
        int min = getMin(array);
        int temp = 0;
        for (int i = 0; i < array.length; i++) {
            temp += array[i];
        }
        return Math.max(max1, temp - min);
    }

}