我正在尝试为下一个问题找到带有分而治之的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(吗？
谢谢你的时间。
如果您遍历数组一次并仅对正数求和，则可以轻松获得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)仍然是正确的。排序确实提供了不遍历数组所有元素的可能性，但这并非在每种情况下都能实现。
想象一下以下数组，它们都是循环排序的，请查看它们下面的模式，它们可能是这里分而治之的解决方案和/或平均情况(大 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);
}
你所要求的是不可能的。
输入数组可能都是正值，这意味着您至少必须读取所有元素并求和。那是O(n(。
即使不是所有的元素都是正的，除非定义不超过O(log n(个元素是正的，否则相同的结论仍然存在。