package com.arc.test;
public class MiniArrayTest {
public static void main(String[] args) {
int[] arr = {-15, 3, 3, -20, 1, -4};
getMiniArray(arr);
}
public static void getMiniArray(int[] arr){
int startIndex = 0;
int endIndex = 0;
int temp = Integer.MAX_VALUE;
int min = 0;
// 如果数组长度为1或2,则最小的连续子集就是自己
if(arr.length <= 2){
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i] + ",");
}
return;
}
// 用index标注出现负数的数组下标,依次比较结果,index将停留在数值最小的地方
// 此时,时间复杂度是O(n)
for(int i = 0; i < arr.length; i++){
if(arr[i] < 0){
min += arr[i];
if(min <= temp){
startIndex = endIndex;
endIndex = i;
temp = min;
min = arr[endIndex];
}
}else{
min += arr[i];
}
}
// 如果endIndex > 0,说明数组中有负数,则把startIndex和endIndex之前的元素打印出来
// 这里,最大时间复杂度(n)
// 所以,总的时间复杂度2O(n),也可以当作O(n)
if(endIndex > 0){
if(startIndex == 0){
for(int i = startIndex; i <= endIndex; i++){
System.out.print(arr[i] + ",");
}
}
// 如果endIndex = 0,说明数组中没有负数,则把连续的最小的两个整数输出,就是最小连续子集合
// 这里,最大时间复杂度(n)
// 所以,总的时间复杂度2O(n),也可以当作O(n)
}else{
endIndex = 1;
min = arr[0] + arr[1];
for(int i = 2; i < arr.length; i++){
if(arr[i - 1] + arr[i] <= min){
min = arr[i] + arr[i - 1];
endIndex = i - 1;
}
}
System.out.println(arr[endIndex - 1] + "," + arr[endIndex]);
}
}
}
不可能的!
我不知道,应该是不可能的!