Question

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

例如：有一组数据｛1，-2，0，9，123｝有正有负，求找出其中连续的子集中和最小的，如｛1，-2，0｝和-1是最小的，并要求时间复杂度为O(n)。

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

追问

非常感谢你的回答，虽然在你设置的数组实验时 答案是正确的 但是 我认为28行起到40行

有些逻辑错误，因为当我置换数组为arr【-1,3,3,-2,1,-4】时 程序就有错误，而且temp 就失去其意义。
恳请您再费些脑力为我解答。非常感谢。

追答

嗯，谢谢提醒。写的比较着急所以不太严谨。但是我想你应该明白我的思路了。你可以自己试试，我想这样才会有进步哦~

Answer 2

不可能的！

追问

能否告诉我为什么不可能 ，有什么逻辑矛盾吗

追答

逻辑矛盾是没有的，只不过要求O(N)谁也设计不出来

Answer 3

我不知道，应该是不可能的！