21.13 Continuous Subarray Sum

Question

• lintcode: (402) Continuous Subarray Sum

Problem Statement

Given an integer array, find a continuous subarray 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 their are duplicate answer, return anyone)

Example

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

题解

和题 Maximum Subarray 几乎一模一样，只是返回值要求不一样。由于需要返回区间索引值，那么显然需要额外变量记录区间起止处。若使用题解2中提到的sum - minSum的区间和更新方式，索引终止处容易得知是sum - minSum > maxSub时的i, 问题是索引起始处如何确定。容易得知索引起始处如果更新，必然在minSum > sum时，但问题在于满足此条件的可能不止一处，所以我们需要先记录这个索引值并在sum - minSum > maxSub时判定索引终止值是否大于索引起始值，不小于则更新。

此题难以一次 bug-free, 需要小心更新索引值。

Java

public class Solution {
    /**
     * @param A an integer array
     * @return  A list of integers includes the index of the first number and the index of the last number
     */
    public ArrayList<Integer> continuousSubarraySum(int[] A) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (A == null || A.length == 0) return result;

        int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
        int first = 0, last = 0;
        int first2 = 0; // candidate for first
        for (int i = 0; i < A.length; i++) {
            if (minSum > sum) {
                minSum = sum;
                first2 = i;
            }
            sum += A[i];
            if (sum - minSum > maxSub) {
                maxSub = sum - minSum;
                last = i;
                // update first if valid
                if (first2 <= last) first = first2;
            }
        }

        result.add(first);
        result.add(last);
        return result;
    }
}

源码分析

除了最后要求的first和last, 我们还需要引入first2作为first可能的候选变量值。

复杂度分析

略