Please help me with this assignment. For this assignment you will implement divide and conquer algorithms: the maximum subarray. For merge sort, you will just implement the algorithm on an array of ints. 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 both an array and 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 array and list are not empty.

public static Triple getMaxSubarray(int[] arr)

This method returns a triple that represents the maximum subarray. The first element of the triple is the index in arr where the maximum subarray starts, the middle element of the triple is where the index in the arr where maximum subarray ends, and the last element of the triple is the maximum subarray sum.

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.java

This file contains a generic Triple class. You will use this to return the starting point, ending point, and sum for the MaxSubFinder class. We use classes like this when we want to have a container that holds different types. Do not modify this 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; }

}

Maximum Subarray findMaxsubarry (arr, low, high) if high==10w return (low, high, arr [low]) else mid= mid point of arr (l-low,l-high,l-sum) = findMaxsubarray (arr,low,mid) (r-low, r-high,r-sum) = findMaxsubarray (arr,mid+1, high) (c-low, c-high,c-sum) = findMaxCrossing (arr,low, mid, high) if l-sum r-sum and l-sum c sum return (l-low, l-high, l-sum) else if r-sum 1-sum and r-sum c-sum return (rlow,rhigh,rsum) else return (c-low, c-high, c-sum) findMaxCrossing (arr, low, mid, high) 1 sum = MIN sum =0 for i= mid downto low sum = sum arr[i] if sum >1 sum 1 sum = sum max-left =i r sum =MIN sum =0 for j=mid+1 to high sum = sum +arr[j] if sum > r-sum r sum = sum max-right =j return (max-left, max-right, 1sum+rsum )