题目:给你一个整数数组 nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和,并输出开始索引与结束索引
注意:子数组
是数组中的一个连续部分
示例1:
输入:nums=[-2,1,-3,4,-1,2,1,-5,4]
输出:6 3 6
解释:
6(连续子数组[4,-1,2,1]和最大为6)
3上述连续子数组的第一个元素在nums中的索引为3
6上述连续子数组的最后一个元素在nums中的索引为6
示例2
输入:nums=[2]
输出:2 0 0
public class MaximumSbuarray {
public static void main(String[] args) {
int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
int pre = nums[0];
int max = nums[0];
int start = 0;
int end = 0;
int startMax = 0;
int endMax = 0;
for (int i = 1; i < nums.length; i++) {
int curNum = nums[i];
//往前走,不断确定序列区间
if (pre + curNum > curNum) {
end = i;
pre += curNum;
} else {
start = i;
end = i;
pre = curNum;
}
//确定最大值
if (pre > max) {
startMax = start;
endMax = end;
max = pre;
}
}
System.out.println("statrMax=" + startMax + "," + "endMax=" + endMax);
System.out.println("max=" + max);
}
}