如何返回最小和连续子数组的子数组而不是和？

Question

我正在研究java中一个相当简单且流行的最小和连续子数组问题。该问题要求创建一个类，并在其中编写一个方法，该方法接受整数数组并返回最小和的连续子数组。一个示例数组，例如 {3, -4, 2, -3, -1, 7, -5} 应该返回：{-4, 2, -3, -1}，因为它的总和是 -6，并且有不是样本数组中总和小于 -6 的子数组。网上有几个针对此问题的教程，例如 https://www.geeksforgeeks.org/smallest-sum-contigious-subarray/#，但这些解决方案返回总和，而不是从原始数组创建的整个子数组。我正在尝试找出如何返回子数组。

这是我到目前为止的代码：

import java.util.ArrayList;

public class Problem1 {
    public static void main(String[] args) {
        int array1[] = { 3, -4, 2, -3, -1, 7, -5 };
        int size1 = array1.length;

        int array2[] = { 1, 2, -1, 3, -6, -1, 4, 5 };
        int size2 = array2.length;

        int array3[] = { 10, -8, 3, -7, 2, -3 };
        int size3 = array3.length;

        System.out.println(smallestSum(array1, size1));
        System.out.println(smallestSum(array2, size2));
        System.out.println(smallestSum(array3, size3));
    }

    static String smallestSum(int array[], int size) {
        int smallEnding = Integer.MAX_VALUE;
        int smallCurrent = Integer.MAX_VALUE;
        ArrayList<Integer> subArray = new ArrayList<Integer>();

        for (int i = 0; i < size; i++) {

            if (smallEnding > 0) {
                smallEnding = array[i];
            } else {
                smallEnding += array[i];
                subArray.add(array[i - 1]);
            }

            smallCurrent = Math.min(smallCurrent, smallEnding);
        }

        return ("The smallest sum contiguous subarray of the array is " +
                subArray.toString() + " with a sum of "
                + Integer.toString(smallCurrent));
    }
}

这是我得到的输出：

The smallest sum contiguous subarray of the array is [-4, 2, -3, -1] with a sum of -6
The smallest sum contiguous subarray of the array is [-1, -6, -1, 4] with a sum of -7
The smallest sum contiguous subarray of the array is [-8, 3, -7, 2] with a sum of -13

我已经弄清楚如何找到最小和的连续子数组并可以正确返回总和，但返回的子数组不正确。子数组对于 array1 是正确的，但对于 array2 和 array3 来说不正确（array2 应读取 [-1, -6]，array3 应读取 [-8, 3, -7, 2, -3]）。我无法弄清楚为什么这适用于 array1 而不适用于其他数组。非常感谢任何帮助或建议。

Answer 1

问题在于您没有正确跟踪最新子数组的开头，因此以与具有最小总和的实际子数组不对应的方式更新元素。

要解决这个问题，您可以存储子数组的开始和结束索引。可能会找到多个，因此您需要：

• 跟踪当前起始索引（当前子数组开始的位置）
• 只要发现较小的总和，就更新实际的开始和结束索引。

然后，您可以将从正确子数组的开头到结尾的元素添加到您的

subArray

列表中。

static String smallestSum(int array[], int size) {
    int smallEnding = Integer.MAX_VALUE;
    int smallCurrent = Integer.MAX_VALUE;
    
    int currentStart = Integer.MAX_VALUE;
    int actualStart = Integer.MAX_VALUE;
    int end = Integer.MAX_VALUE;
    
    ArrayList<Integer> subArray = new ArrayList<Integer>();
    
    for (int i = 0; i < size; i++) {
    
        // this happens each time we start a new subarray
        if (smallEnding > 0) {
            smallEnding = array[i];
            // therefore `i` must be the newest starting index
            currentStart = i; 
        } else {
            smallEnding += array[i];
        }
    
        // current subarray sum becomes smaller, so we
        // need to update the actual start and end indices
        if (smallEnding < smallCurrent) {
            actualStart = currentStart;
            end = i;
        }
        
        smallCurrent = Math.min(smallCurrent, smallEnding);
    }

    // add the elements to the ArrayList
    for (int i = actualStart; i <= end; i++) {
        subArray.add(array[i]);
    }
    
    return ("The smallest sum contiguous subarray of the array is " +
                subArray.toString() + " with a sum of "
                + Integer.toString(smallCurrent));
}

这段代码给了我以下输出：

The smallest sum contiguous subarray of the array is [-4, 2, -3, -1] with a sum of -6
The smallest sum contiguous subarray of the array is [-6, -1] with a sum of -7
The smallest sum contiguous subarray of the array is [-8, 3, -7, 2, -3] with a sum of -13