Max Sum Subarray Index
给定一个整数数组,请找出一个连续子数组,使得该子数组的和最大。输出答案时,请分别返回第一个数字和最后一个数字的值。(如果两个相同的答案,请返回其中任意一个)
样例
给定 [-3, 1, 3, -3, 4], 返回[1,4].
Solution
和最大子数组类似,只是这个要记录下标,最大子数组是求和
Complexity
时间复杂度 O(n),空间复杂度 O(1)
Code
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> res = new ArrayList<Integer>();
if (A == null || A.length == 0) {
return res;
}
int sum = A[0];
int max = sum;
int start = 0, end = 0;
res.add(0);
res.add(0);
for (int i = 1; i < A.length; i++) {
if (sum > max) {
res.set(0, start);
res.set(1, i-1);
max = sum;
}
if (sum < 0) {
sum = 0;
start = i;
end = i;
}
sum += A[i];
}
if (sum > max) {
res.set(0, start);
res.set(1, A.length-1);
}
return res;
}
}