/**
1. 环形-> 把数组复制到自己尾部;  子数组和-> 处理后的数组长度最大为n的子数组和
2. 怎么快速求区间和 -> 前缀和 -> sum(i~j) = prefix[i] - prefix[j-1] (i-j+1 <= n+1) -> 固定j后求最小的prefix[j-1]
3. 怎么动态求最小的prefix[j-1]? 单调队列求最小值
    3.1 当i-n > queue.peekFirst() 时, 说明已经超出 长度n的范围, queue.pollFirst, 
    3.2 更新结果
    3.3 压入是保持队列单调递减, 如果压入的值比队尾的值还小此时队尾一定不是答案, while-queue.pollLast(), offer(x)
*/

/**
1. 思考一个问题, 环形数组中 总和 - 最大子段和 = 最小子段和. (感觉这个解释有些牵强....)
    1.1 我们选最大子段和的时候是基于代价大于0的, 
    1.2 那挑剩下的就是 代价等于0 的和代价小于0的, 代价等于0的没有影响
    1.3 最小子段和就是代价小于0的和

2. 所以分两种情况讨论:
    2.1 不用循环情况的下的最大子段和 sum1
    2.2 需要循环情况下的总和 - 最小子段和 sum - sum2
    2.3 特判下全是负数时, sum == sum2 , 此时输出sum1
*/

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        // return dp(A);
        // return monoQueue(A);
    }

    public int dp(int[] A){
        int sum = 0, sum1 = Integer.MIN_VALUE, sum2 = Integer.MAX_VALUE;
        for (int i = 0, cur1 = 0, cur2 = 0; i < A.length ; i++){
            cur1 = A[i] + Math.max(cur1, 0);
            sum1 = Math.max(cur1, sum1);

            cur2 = A[i] + Math.min(cur2, 0);
            sum2 = Math.min(cur2, sum2);

            sum += A[i];
        }
        return sum == sum2 ? sum1 : Math.max(sum1, sum-sum2);
    }

    public int monoQueue(int[] A){
        List<Integer> c = new ArrayList<>();
        int n = A.length;
        for (int i = 0; i < n ; i++) c.add(A[i]);
        for (int i = 0; i < n ; i++) c.add(A[i]);
        for (int i = 1 ; i < c.size(); i++) c.set(i, c.get(i) + c.get(i-1));

        Deque<Integer> queue = new LinkedList<>();
        int result = Integer.MIN_VALUE;
        for (int i = 0 ; i < c.size() ; i++){
            // i-j+1 <= n+1  ->   i-j <= n  -> i-n <=j ,不符合时弹出
            if (!queue.isEmpty() && i - n > queue.peekFirst()) queue.pollFirst();
            // result update why in this?  因为压入新值时可能把队头更新掉
            result = Math.max(result, c.get(i) - (queue.isEmpty()? 0 : c.get(queue.peekFirst())));

            while (!queue.isEmpty() && c.get(queue.peekLast()) > c.get(i)) queue.pollLast();
            queue.offerLast(i);
        }
        return result;
    }
}