用java编程:输入一个集合,可以有正数有负数,写一个程序 输出集合内所有数值的和最小的连续子集有一组数

2024-11-26 03:49:22
推荐回答(3个)
回答1:

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]);
}
}
}

回答2:

不可能的!

回答3:

我不知道,应该是不可能的!