For this problem, you will implement divide and conquer algorithms: 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:

package divideandconquer;

public class LinkedList { //inner class that creates Nodes for the LinkedList static class Node { int data; Node next; Node prev; Node(int data) { this.data = data; next = null; prev = null; } Node(int data, Node next,Node prev) { this.data = data; this.next = next; this.prev = prev; } } //Node that starts the LinkedList Node head; Node tail; //Constructor that converts an int array to a LinkedList LinkedList(int[] nums) { for(int i: nums) { insert(i); } } //No argument constructor LinkedList() { head = null; } /* * Creates a sublist from the LinkedList from the start node * to the end node * Running sublist on 12345 with start = 2 and end =4 * returns the new LinkedList:234 */ LinkedList subList(Node start,Node end) { LinkedList sub = new LinkedList(); Node current = head; while(current!=start) { current = current.next; } sub.insert(current.data); if(start==end) return sub; current = current.next; while(current!=end) { sub.insert(current.data); current = current.next; } sub.insert(current.data); return sub; } /* * insert a new node at the end of the LinkedList * with data equal to i */ void insert(int i) { Node node = new Node(i); if(isEmpty()) head = node; else { tail.next = node; node.prev = tail; } tail = node; } boolean isEmpty() { return head==null&&tail==null; } //finds the middle node in the linked list Node middle(Node low,Node high) { int size = 0; Node current = low; while(current!=high) { size++; current = current.next; } int half = size/2; current = low; while(half>0) { current = current.next; half--; } return current; } //string representation of the linked list //useful for debugging public String toString() { String s = ""; if(isEmpty()) return s; Node current = head; while(current!=null) { s = s+current.data + ""; current = current.next; } return s.substring(0,s.length()-3); }

}

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 )