我正在嘗試使用分而治之的 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) 嗎？感謝您的時間。
2 回答
不負相思意
TA貢獻1777條經驗 獲得超10個贊
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);
}
手掌心
TA貢獻1942條經驗 獲得超3個贊
你所要求的是不可能的。
輸入數組可能都是正值，這意味著您至少必須讀取所有元素并對它們求和。那是 O(n)。
即使并非所有元素都是正數，除非定義不超過 O(log n) 個元素是正數，否則仍會得出相同的結論。
添加回答
舉報
0/150
提交
取消