Continuous Subarray Sum II

Given an circular integer array (the next element of the last element is the first element), find a continuous subarray in it, where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number.

If duplicate answers exist, return any of them.

 

Example

Give [3, 1, -100, -3, 4], return [4,1].

很有意思的题目,是Continuous Subarray Sum的follow up.主要区别在这里是将普通数组变化为了circular integer array. 我们最终求得的子数组index pair [start, end]中可能start > end. 这种情况需要怎么处理.

首先想到的思路是求非循环数组中的和最小的连续subarray, 这样不在这个子数组中的子数字就是最大子数组中的元素. 这种解法在最终结果start< end 时无法求出最优结果(因为求最小subarray的解法已经默认 max subarray 是circular的).

综上: 我们可以先求出非circular的情况下的max subarray, 之后我们用求补的方法求出非circular情况下的min subarray, 可以在求解时检查是否减去这个min subarray之后其余数字组成的circular subarray大于非circular的max subarray, 是则更新. 其中每次求解都是用的Continuous Subarray Sum中的local, global DP.

需要谨慎一种情况,在所有数字都是负数时, 全部数组组成了min subarray,但是这是max subarray没有元素,是错误的.时间复杂度O(n), 空间复杂度O(1).代码如下:

class Solution:
    # @param {int[]} A an integer array
    # @return {int[]}  A list of integers includes the index of the 
    #                  first number and the index of the last number
    def continuousSubarraySumII(self, A):
        # solution1, find a continous subarray in the straight array which has the smallest sum, wrong
        if not A:
            return [0, 0]
        start = 0
        end = 0
        res = [0, 0]
        import sys
        localMax = 0
        globalMax = -sys.maxint
        total = sum(A)
        for i in xrange(len(A)):
            if localMax < 0:
                start = i
                end = i
                localMax = A[i]
            else:
                localMax += A[i]
                end = i
            if localMax > globalMax:
                res[0] = start
                res[1] = end
                globalMax = localMax
        start = 0
        end = 0
        localMin = sys.maxint
        for i in xrange(len(A)):
            if localMin > 0:
                localMin = A[i]
                start = i
                end = i
            else:
                localMin += A[i]
                end = i
            if start == 0 and end == len(A) - 1: continue #the number in array are all negative
            if total - localMin > globalMax:
                globalMax = total - localMin
                res[0] = end + 1
                res[1] = start - 1