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

Question

我正在尝试通过分而治之为下一个问题找到 O(N) 的解决方案：

给定一个循环排序的数组，我需要它的正数之和。即：

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 conquer public 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).

即使不是所有的元素都是正的，除非定义了不超过 O(log n) 个元素是正的，同样的结论仍然存在。

Answer 2

如果您遍历一次数组并仅对正数求和，则可以轻松获得 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) 仍然是正确的。排序确实提供了不遍历数组所有元素的可能性，但并非在所有情况下都可以实现。

想象一下下面的数组，它们都是循环排序的，请看看它们下面的模式，它们可能是这里分而治之的解决方案的关键and/or 平均情况 (Big Theta) 小于 n，而 最坏情况 (Big 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);
}

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

Divide & Conquer algorithm for finding sum of positive numbers in circularly sorted array

java

arrays

sorting

algorithm

divide-and-conquer