用于查找循环排序数组中正数之和的分而治之算法

Question

我正在尝试使用分而治之的 O(N) 解决方案来解决下一个问题：给定一个循环排序的数组，我需要它的正数之和。IE：If the array is: {-2, 0, 3, 4, 11, 13, -23, -15, -8}Then the algorithm should return 31.我认为我已经通过以下代码接近它，但它奇怪地返回 -17 并且我无法找到问题调试：public class Main {private static final int[] TEST_VECTOR = new int[]{-2, 0, 3, 4, 11, 13, -23, -15, -8};public static int sumPositives2(int[] vector) {    return maximumSum(vector,0, vector.length - 1);}// Function to find Maximum subarray sum using// divide and conquerpublic static int maximumSum(int[] A, int left, int right){    // If array contains only one element    if (right == left) {        return A[left];    }    // Find middle element of the array    int mid = (left + right) / 2;    // Find maximum subarray sum for the left subarray    // including the middle element    int leftMax = Integer.MIN_VALUE;    int sum = 0;    for (int i = mid; i >= left; i--)    {        if(A[i] > 0) {            sum += A[i];        }    }    // Find maximum subarray sum for the right subarray    // excluding the middle element    int rightMax = Integer.MIN_VALUE;    sum = 0;    // reset sum to 0    for (int i = mid + 1; i <= right; i++)    {        if(A[i] > 0) {            sum += A[i];        }    }    // Recursively find the maximum subarray sum for left    // subarray and right subarray and tale maximum    int maxLeftRight = maximumSum(A, left, mid) +            maximumSum(A, mid + 1, right);    // return maximum of the three    return maxLeftRight + leftMax + rightMax;}public static void main(String[] args){    System.out.println("The Maximum sum of the subarray is " +            maximumSum(TEST_VECTOR, 0, TEST_VECTOR.length - 1));//Should be 31}}编辑：这个解决方案是 O(N) 吗？感谢您的时间。

Answer 1

O(n)如果您遍历该数组一次并仅对正数求和，您就可以轻松获得解决方案。增强for循环似乎合适：

public static void main(String[] args) {

    int[] circularlySortedArray = {-2, 0, 3, 4, 11, 13, -23, -15, -8};

    // define a variable for the sum

    int sumOfPositives = 0;

    // go through all numbers in the array (n numbers)

    for (int number : circularlySortedArray) {

        // check if the number is positive

        if (number >= 0) {

            // and add it to the sum variable

            sumOfPositives += number;

        }

    }

    // then print the result

    System.out.println("The sum of positive numbers is " + sumOfPositives);

}

这种情况下的输出是

The sum of positive numbers is 31

排序对算法没有任何影响。

您的解决方案是，O(n)如果它有效，但您实际上不必在这里分而治之，因为无论如何它都不能完成O(n)，它不是二分搜索。

编辑

由于上面的文本和代码似乎不够令人满意，我重新思考了我在这里关于分而治之的陈述。该任务可能只需不到n几步即可完成，但O(n)仍然是正确的。排序确实提供了不遍历数组的所有元素的可能性，但这并不是在所有情况下都可以实现。

想象一下下面的数组，它们都是循环排序的，请看一下它们下面的模式，它们可能是这里分而治之解决方案和/或平均情况（Big Theta）解决方案的关键小于n，而最坏的情况（大 O）仍然会存在O(n)……

这些例子都有n = 7元素，每个例子都有p = 4正元素（包括0）和l = 3负元素。遍历所有这些将始终是O(n)，这将在O(6)这里。在某些情况下，排序提供了有关数组末尾内容的信息，这使程序员能够在某些情况下将最佳情况（Big Omega）减少到O(p + 1) = O(p) = O(4)：

下面的数组需要 n 步，因为必须检查每个元素

{-3, -2, -1, 0, 1, 2, 3}

  n   n   n  p  p  p  p

下一个示例需要采取n - 1步骤，因为在所有正数之后还有两个负数，您只需找到第一个即可满足条件break。那是因为较低的指数已经存在负数。

{-1, 0, 1, 2, 3, -2, -3}

  n  p  p  p  p   n   n

下一个仅需要p + 1（这意味着O(p + 1) = O(p)）步，因为您可以break在找到的第一个负数处进行循环。为什么？因为数组从尽可能小的正数（根据定义）开始，找到的第一个负数表示不需要进一步处理。

{0, 1, 2, 3, -1, -2, -3}

 p  p  p  p   n   n   n

最后一个示例n再次需要步骤，因为您正在查找位于数组开头和结尾的正数。没有机会直接知道它们处于哪个索引。

{3, -3, -2, -1, 0, 1, 2}

 p   n   n   n  p  p  p

（我知道）优化平均情况的唯一方法是break根据可能的模式实现循环的条件。所以存储索引并根据它们进行检查，但我认为效果不会那么大。

这是我的第一个方法，可能会通过多种方式进行优化，我只尝试过此编辑的示例：

public static void main(String[] args) {

    int[] circularlySortedArray = { 0, 1, 2, 3, -1, -2, -3 };

    // define a variable for the sum of positive values

    int sumOfPositives = 0;

    // define a variable for the lowest index of a positive number

    int firstPositiveIndex = -1;

    // define a variable for the lowest positive number found

    int smallesPositiveNumber = 0;

    // start iterating the array

    for (int i = 0; i < circularlySortedArray.length; i++) {

        System.out.println("Current index: " + i 

                + ", current value: " + circularlySortedArray[i]);

        // provide a variable for the current number to make this code a little more

        // readable

        int number = circularlySortedArray[i];

        // check if the current number is positive

        if (number >= 0) {

            // add it to the sum

            sumOfPositives += number;

            System.out.println("Added " + number 

                    + " to sumOfPositives (now: " + sumOfPositives + ")");

            // check if it is the first positive number found

            if (firstPositiveIndex < 0) {

                // if yes, set the variable value accordingly

                System.out.println("First and smallest positive number (" 

                                    + number 

                                    + ") found at index " 

                                    + i);

                firstPositiveIndex = i;

                smallesPositiveNumber = number;

            }

            System.out.println("————————————————————————————————");

        } else {

            // break conditions based on index & value of the smallest positive number found

            if (i > firstPositiveIndex && firstPositiveIndex > 0) {

                System.out.println("Stopped the loop at index " + i);

                break;

            } else if (smallesPositiveNumber == 0 && firstPositiveIndex == 0) {

                System.out.println("Stopped the loop at index " + i);

                break;

            }

            System.out.println(number + " is not positive, skip it");

            System.out.println("————————————————————————————————");

            continue;

        }

    }

    System.out.println("The sum of positive numbers is " + sumOfPositives);

}

Answer 2

你所要求的是不可能的。

输入数组可能都是正值，这意味着您至少必须读取所有元素并对它们求和。那是 O(n)。

即使并非所有元素都是正数，除非定义不超过 O(log n) 个元素是正数，否则仍会得出相同的结论。