I am trying to find the O(N) solution with Divide & Conquer for the next problem:
Given a circularly sorted array, I need the sum of the positive numbers on it. i.e:
If the array is: {-2, 0, 3, 4, 11, 13, -23, -15, -8}
Then the algorithm should return 31.
I think I'm close to it with the following code, but it's weirdly returning -17 and I cannot find the problem debugging:
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
}
}
Edit: Would this solution be O(N)?
Thank you for your time.
You can easily get an O(n) solution if you go through the array once and sum up only positive numbers. An enhanced for loop seems suitable:
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 output in this case is
The sum of positive numbers is 31
The sorting does not have any influence on the algorithm.
Your solution would be O(n) if it was working, but you don't really have to divide and conquer here because it cannot be done in less than O(n) anyway, it's not a binary search.
EDIT
Since the text and code above seems not to be satisfying enough, I re-thought my statement about divide and conquer here. The task may be done in less than n steps, but O(n) will still be correct. The sorting does provide a possibility of not going through all elements of the array, but that won't be achievable in every case.
Imagine the following arrays, which are all circularly sorted, and please have a look at the patterns below them, they may be the key to a divide-and-conquer solution here and/or to a solution with an average case (Big Theta) of less than n, while the worst case (Big O) will still stay O(n)…
The examples all have n = 7 elements and each one has p = 4 positive elements (including 0) and l = 3 negative elements. Iterating through all of them will always be O(n), which would be O(6) here. In some of the cases, the sorting provides information about what's at the end of the array, which enables a programmer to reduce the best case (Big Omega) to O(p + 1) = O(p) = O(4) in some of the situations:
The following array takes n steps because one has to check every element
{-3, -2, -1, 0, 1, 2, 3}
n n n p p p p
The next example takes n - 1 steps, because there is are two negative numbers after all the positives and you only have to find the first one in order to meet a break condition. That's because there was a negative number already at a lower index.
{-1, 0, 1, 2, 3, -2, -3}
n p p p p n n
This next one takes only p + 1 (which means O(p + 1) = O(p)) steps because you can break the loop at the first negative number found. Why? Because the array starts with the smallest possible number that is positive (by definition) and the first negative number found indicates no need for further processing.
{0, 1, 2, 3, -1, -2, -3}
p p p p n n n
This last example requires n steps again, because you are looking for positive numbers which are at the beginning and at the end of the array. There is no chance of directly knowing at which index they are.
{3, -3, -2, -1, 0, 1, 2}
p n n n p p p
The only way (I know) to optimize the average case would be implementing the break conditions of the loop according to the possible patterns. So store indexes and do checks based on them, but I think the effect won't be that huge.
This is my first approach, may be optimized in several ways, I have only tried it with the examples of this edit:
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);
}