# Continuous Subarray Sum II

## Question

### Problem Statement

Given an integer array, find a continuous rotate 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. The answer can be rorate array or non- rorate array)

#### Example

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

## 题解

Continuous Subarray Sum 的 follow up, 这道题 AC 率极低，真是磨人的小妖精。在上题的基础上容易想到可以将firstlast分四种情况讨论，然后再逆向求大于0的最大和即可，但是这种想法忽略了一种情况——旋转后的最大值可能由两段子数组和构成，而这种情况如果用上题的解法则会被忽略。

### 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> continuousSubarraySumII(int[] A) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (A == null || A.length == 0) return result;
// maximal subarray sum
ArrayList<Integer> sub1 = subSum(A, 1);
// minimal subarray sum
ArrayList<Integer> sub2 = subSum(A, -1);
int first = 0, last = 0;
if (sub1.get(3) - sub2.get(2) > sub1.get(2)) {
last = sub2.get(0) - 1;
first = sub2.get(1) + 1;
} else {
first = sub1.get(0);
last = sub1.get(1);
}
// corner case(all elements are negtive)
if (last == -1 && first == A.length) {
first = sub1.get(0);
last = sub1.get(1);
}

return result;
}

private ArrayList<Integer> subSum(int[] A, int sign) {
ArrayList<Integer> result = new ArrayList<Integer>();
// find the max/min subarray sum from [0...A.length]
int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
if (sign == -1) maxSub = Integer.MAX_VALUE;
int first = 0, last = 0;
int first2 = 0; // candidate for first
for (int i = 0; i < A.length; i++) {
if (sign * minSum > sign * sum) {
minSum = sum;
first2 = i;
}
sum += A[i];
if (sign * (sum - minSum) > sign * maxSub) {
maxSub = sum - minSum;
last = i;
// update first if valid
if (first2 <= last) first = first2;
}
}
return result;
}
}