用于查找循环排序数组中正数之和的分而治之算法
我正在尝试使用分而治之的 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 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) 吗？
感谢您的时间。
婷婷同学_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)仍然是正确的。排序确实提供了不遍历数组的所有元素的可能性，但这并不是在所有情况下都可以实现。想象一下下面的数组，它们都是循环排序的，请看一下它们下面的模式，它们可能是这里分而治之解决方案和/或平均情况（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);} -
手掌心
你所要求的是不可能的。输入数组可能都是正值，这意味着您至少必须读取所有元素并对它们求和。那是 O(n)。即使并非所有元素都是正数，除非定义不超过 O(log n) 个元素是正数，否则仍会得出相同的结论。
随时随地看视频慕课网APP
相关分类
Java