For this Problem, you will implement a brute force solution to the maximum-subarray problem that runs in O(n2) time (i.e., your solutions should have two nested loops). You will implement this solution for an array of ints and a simple LinkedList of ints. To get started, import the two starter files into the subarray package you created in a new Java Project. Please do not change any of the method signatures or any code in the provided LinkedList class. Implement the two methods described below.

public LinkedList findMaximumSubList(LinkedList nums)

This method should return a new LinkedList that represents the maximum sublist of the given LinkedList, nums. For example, the maximum sublist of 13->-3->-25->-20->-3->-16->-23->18->20->-7->12->-5->-22->15->-4->7

is 18->20->-7->12

public int[] findMaximumSubArray(int[] nums)

This method should return a new int[] that represents the maximum subarray of the given int[], nums. For example, the maximum subarray of [13,-3,-25,-20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]

is [18,20,-7,12]

package subarray;

public class LinkedList { //inner class that creates Nodes for the LinkedList static class Node { int data; Node next; Node(int data) { this.data = data; next = null; } Node(int data, Node next) { this.data = data; this.next = next; } } //Node that starts the LinkedList Node head; //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 1->2->3->4->5 with start = 2 and end =4 * returns the new LinkedList:2->3->4 */ 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) { if(head==null) { head = new Node(i); } else { Node current = head; while(current.next != null) { current = current.next; } current.next = new Node(i); } } boolean isEmpty() { return head==null; } //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()-2); }

}

FindMaxSub - Notepad File Edit Format View Help package subarray; import subarray. LinkedList. Node; public class FindMaxsub \{ public static LinkedList findMaximumSubList(LinkedList nums) \{ return new LinkedList(); \} public static int [] findMaximumSubArray(int [] nums) \{ return new int [] 3 \} FindMaxSub - Notepad File Edit Format View Help package subarray; import subarray. LinkedList. Node; public class FindMaxsub \{ public static LinkedList findMaximumSubList(LinkedList nums) \{ return new LinkedList(); \} public static int [] findMaximumSubArray(int [] nums) \{ return new int [] 3 \}