For this problem, you will implement divide and conquer algorithms: the maximum subarray. I have provided the pseudo code for algorithms below. You will need to handle cases of all sizes, not just powers of 2. Maximum Subarray using Divide and Conquer Create a class called MaxSubFinder in the divideandconquer package. This class will implement the maximum subarray problem on a linked list using the pseudocode described above. Implement the following methods with the exact signatures below. You will need to create private helper methods to do most of the work. You can assume that the list are not empty. public static Triple getMaxSubList(LinkedList list) This method returns a triple that represents the maximum sub list. The first element of the triple is the list node where the maximum sublist starts, the middle element of the triple is the list node where the maximum sublist ends, and the last element of the triple is the maximum sublist sum . Triple class: package divideandconquer; public class Triple { First first; Middle middle; Last last; public Triple(First first, Middle middle, Last last) { this.first= first; this.middle = middle; this.last = last; } public First getFirst() { return first; } public void setFirst(First first) { this.first = first; } public Middle getMiddle() { return middle; } public void setMiddle(Middle middle) { this.middle = middle; } public Last getLast() { return last; } public void setLast(Last last) { this.last = last; } } LinkedList Class:
For this problem, you will implement divide and conquer
2.
Maximum Subarray using Divide and Conquer
Create a class called MaxSubFinder in the divideandconquer package. This class will
implement the maximum subarray problem on a linked list using the
pseudocode described above. Implement the following methods with the exact signatures
below. You will need to create private helper methods to do most of the work. You can
assume that the list are not empty.
public static Triple<Node,Node,Integer> getMaxSubList(LinkedList list)
This method returns a triple that represents the maximum sub list. The first element of the
triple is the list node where the maximum sublist starts, the middle element of the triple is
the list node where the maximum sublist ends, and the last element of the triple is the
maximum sublist sum .
Triple class:
package divideandconquer;
public class Triple<First,Middle,Last> {
First first;
Middle middle;
Last last;
public Triple(First first, Middle middle, Last last) {
this.first= first;
this.middle = middle;
this.last = last;
}
public First getFirst() {
return first;
}
public void setFirst(First first) {
this.first = first;
}
public Middle getMiddle() {
return middle;
}
public void setMiddle(Middle middle) {
this.middle = middle;
}
public Last getLast() {
return last;
}
public void setLast(Last last) {
this.last = last;
}
}
LinkedList Class:
![Maximum Subarray
findMaxSubarry (arr, low, high)
if high-low
else
return (low high, arr [low])
mid= mid point of arr
(1-low, 1-high, 1-sum)
(r-low, r-high, r-sum)
(c-low, c-high, c-sum)
if 1-sum 2 r-sum and
else
findMaxCrossing (arr, low, mid, high)
1-sum = MIN
0
sum =
for i mid downto low
sum = sum arr[i]
if sum > 1-sum
return (1-low, l-high, 1-sum)
else if r-sum ≥l-sum and r-sum ≥c-sum
return (r-low, r-high, r-sum)
return (c-low, c-high, c-sum)
MIN
1-sum = sum
max-left
r-sum =
sum =
0
for j=mid+1 to high
=
i
low, mid)
mid+1, high)
findMaxCrossing (arr, low, mid, high)
1-sum 2 c-sum
sum = sum + arr[j]
if sum > r-sum
=
=
findMaxSubarray(arr,
findMaxSubarray(arr,
=
r-sum sum
max-right = j
return (max-left, max-right, 1-sum+r-sum);](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F165f5551-99fc-4800-9810-1597ce53807c%2Ff14eac02-1e41-480d-aebb-0e7f8ef9f2f3%2F2kk5div_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
In the following code, it errors at
/ Return the maximum subarray among the left, right, and cross subarrays
if (left.getLast() >= right.getLast() && left.getLast() >= cross.getLast()) {
returnleft;
} else if (right.getLast() >= left.getLast() && right.getLast() >= cross.getLast()) {
returnright;
} else {
returncross;
}
Code:
publicstatic Triple<Node,Node,Integer> getMaxSubList(LinkedListlist) {
// If the list is null or empty, return a Triple with all values set to 0
if (list == null || list.isEmpty()) {
returnnew Triple(0, 0, 0);
}
// Call the private helper method to find the maximum subarray
returnfindMaxSubList(list, 0, list.size() - 1);
}
// This is a recursive helper method that divides the list into smaller subarrays
// and finds the maximum subarray of each subarray. It then combines these maximum subarrays
// to find the maximum subarray of the entire list.
privatestaticTriple findMaxSubList(LinkedListlist, intlow, inthigh) {
// Base case: if the subarray has only one element, return that element as the maximum subarray
if (low == high) {
returnnew Triple(low, high, list.get(low));
}
// Calculate the middle index of the subarray
intmid = (low + high) / 2;
// Recursively find the maximum subarray of the left and right halves of the subarray,
// and the maximum subarray that crosses the middle of the subarray
Tripleleft = findMaxSubList(list, low, mid);
Tripleright = findMaxSubList(list, mid + 1, high);
Triplecross = findMaxCrossingList(list, low, mid, high);
// Return the maximum subarray among the left, right, and cross subarrays
if (left.getLast() >= right.getLast() && left.getLast() >= cross.getLast()) {
returnleft;
} else if (right.getLast() >= left.getLast() && right.getLast() >= cross.getLast()) {
returnright;
} else {
returncross;
}
}
// This method finds the maximum subarray that crosses the middle of the subarray
privatestaticTriple findMaxCrossingList(LinkedList<Integer> list, intlow, intmid, inthigh) {
// Initialize variables to keep track of the maximum sum on the left and right sides of the middle
intleftSum = Integer.MIN_VALUE;
intrightSum = Integer.MIN_VALUE;
// Initialize variables to keep track of the starting and ending indices of the maximum subarray
intmaxLeft = 0;
intmaxRight = 0;
// Find the maximum sum on the left side of the middle
intsum = 0;
for (inti = mid; i >= low; i--) {
sum += list.get(i);
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
// Find the maximum sum on the right side of the middle
sum = 0;
for (intj = mid + 1; j <= high; j++) {
sum += list.get(j);
if (sum > rightSum) {
rightSum = sum;
maxRight = j;
}
}
// Return a Triple with the starting and ending indices of the maximum subarray that crosses the middle,
// and the sum of the maximum subarray
returnnew Triple(maxLeft, maxRight, leftSum + rightSum);
}
by Bartleby ExpertI get an error at the followinf code.. it says >= is undefined for the argument type.
// Return the maximum subarray among the left, right, and cross subarrays
if (left.getLast() >= right.getLast() && left.getLast() >= cross.getLast()) {
returnleft;
} else if (right.getLast() >= left.getLast() && right.getLast() >= cross.getLast()) {
returnright;
} else {
returncross;
}
by Bartleby Experti get 2 errors at the following line. How do i correct?
public static Triple getMaxSubList(LinkedList<Integer> list) {
-The type LinkList is not generic; it can't be parameterized with arguments <Integer>
-Triple is a raw type, references to eneric tye Triple <First, Middle, Last> should be parameterized
by Bartleby Expertcan you help with the code for getMaxSubList as well?
by Bartleby Expert
