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); } }
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
public class FindMaxSub {
}
subarray.LinkedList.Node;
public static Linked List findMaximumSubList (Linked List nums) {
return new LinkedList();
}
public static int[] findMaximumSubArray (int[] nums) {
return new int[0];
}](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F165f5551-99fc-4800-9810-1597ce53807c%2Fca56592e-0626-41b2-99c1-c54ded7ea8cd%2Fvv4ste_processed.png&w=3840&q=75)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
