Hello, I am having difficulty with this problem. I\'m trying to figure out a way
ID: 3620737 • Letter: H
Question
Hello, I am having difficulty with this problem. I'm trying to figure out a way to implement this into Java and keep the complexity at O(N).The problem is:
Design efficient algorithms that take an array of positive integers a, and determine a. The maximum value of a[j] + a[i], with j >= i b. The maximum value of a[j] - a[i], with j >= i c. The maximum value of a[j] * a[i], with j >= i d. The maximum value of a[j] / a[i], with j >= i Hopefully someone out there understands this problem better than I do. Thanks in advance!
Design efficient algorithms that take an array of positive integers a, and determine a. The maximum value of a[j] + a[i], with j >= i b. The maximum value of a[j] - a[i], with j >= i c. The maximum value of a[j] * a[i], with j >= i d. The maximum value of a[j] / a[i], with j >= i Hopefully someone out there understands this problem better than I do. Thanks in advance! c. The maximum value of a[j] * a[i], with j >= i d. The maximum value of a[j] / a[i], with j >= i Hopefully someone out there understands this problem better than I do. Thanks in advance!
Explanation / Answer
The hard part is sorting the array but since you're told to keep the complexity at O(N) you're going to be limited to Bucket Sort, Pigeonhole Sort, Counting Sort and a few others (check wikipedia for a rundown on the different sorts and there complexity). Pigeonhole Sort is the simplest to implement of all the O(N) but require integers. Since the problem requires integers as well you should use it here. Simply declare a second array (sorted) initialized to all zeros that has the same size as the max value of the original array of integers (original). This means you will probably need to traverse it once initially just to find the largest number. Then traverse original and increment each index in sorted every time you come across that value. The values in original correspond to the indices of sorted. The frequency of values in original correspond to the values in sorted. All in all this will be something like O(3N) in the worst case. Once to find the max value of original, once to fill in sorted, and a final traversal to answer each of the questions. O(3N) still counts as O(N) though. for (int current : original) { sorted[current]++; } Now remember that sorted will have zeros in all the spots that don't have values in original so that your functions that actually answer questions a-d will have to check and make sure. int maxAdditionValue(int[] sorted) { for(int i = (sorted.length - 1) ; i >= 0 ; i--) // Start from the top for addition/multiplication { if (sorted[i] != 0) { if (sorted[i] = 2) return i * 2; else { for (int j = i - 1 ; i >= 0 ; i--) { if (sorted[j] != 0) return j + i; } } } return 0; // This means the array is empty or there was not more than 1 element. } For division and subtraction you need to do the same thing but the inner loop that finds the second value is going to start from the bottom instead of the top. Good luck!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.