Given a linked list, the task is to find the maximum sum for any contiguous nodes.
Examples:
Input: -2 -> -3 -> 4 -> -1 -> -2 -> 1 -> 5 -> -3 -> NULL
Output: 7
4 -> -1 -> -2 -> 1 -> 5 is the sub-list with the given sum.Input: 1 -> 2 -> 3 -> 4 -> NULL
Output: 10
Approach: Kadane’s algorithm has been discussed in this article to work on arrays to find the maximum sub-array sum but it can be modified to work on linked lists too. Since Kadane’s algorithm doesn’t require to access random elements, it is also applicable on the linked lists in linear time.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// A linked list nodeclass Node {public: int data; Node* next;};/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */void append(Node** head_ref, int new_data){ // Allocate node Node* new_node = new Node(); Node* last = *head_ref; /* used in step 5*/ // Put in the data new_node->data = new_data; /* This new node is going to be the last node, so make next of it as NULL*/ new_node->next = NULL; /* If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return; } // Else traverse till the last node while (last->next != NULL) last = last->next; // Change the next of last node last->next = new_node; return;}// Function to return the maximum contiguous// nodes sum in the given linked listint MaxContiguousNodeSum(Node* head){ // If the list is empty if (head == NULL) return 0; // If the list contains a single element if (head->next == NULL) return head->data; // max_ending_here will store the maximum sum // ending at the current node, currently it // will be initialised to the maximum sum ending // at the first node which is the first node's value int max_ending_here = head->data; // max_so_far will store the maximum sum of // contiguous nodes so far which is the required // answer at the end of the linked list traversal int max_so_far = head->data; // Starting from the second node head = head->next; // While there are nodes in linked list while (head != NULL) { // max_ending_here will be the maximum of either // the current node's value or the current node's // value added with the max_ending_here // for the previous node max_ending_here = max(head->data, max_ending_here + head->data); // Update the maximum sum so far max_so_far = max(max_ending_here, max_so_far); // Get to the next node head = head->next; } // Return the maximum sum so far return max_so_far;}// Driver codeint main(){ // Create the linked list Node* head = NULL; append(&head, -2); append(&head, -3); append(&head, 4); append(&head, -1); append(&head, -2); append(&head, 1); append(&head, 5); append(&head, -3); cout << MaxContiguousNodeSum(head); return 0;} |
Java
// Java implementation of the approachclass GFG{// A linked list nodestatic class Node { int data; Node next;};/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */static Node append(Node head_ref, int new_data){ // Allocate node Node new_node = new Node(); Node last = head_ref; /* used in step 5*/ // Put in the data new_node.data = new_data; /* This new node is going to be the last node, so make next of it as null*/ new_node.next = null; /* If the Linked List is empty, then make the new node as head */ if (head_ref == null) { head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; return head_ref;}// Function to return the maximum contiguous// nodes sum in the given linked liststatic int MaxContiguousNodeSum(Node head){ // If the list is empty if (head == null) return 0; // If the list contains a single element if (head.next == null) return head.data; // max_ending_here will store the maximum sum // ending at the current node, currently it // will be initialised to the maximum sum ending // at the first node which is the first node's value int max_ending_here = head.data; // max_so_far will store the maximum sum of // contiguous nodes so far which is the required // answer at the end of the linked list traversal int max_so_far = head.data; // Starting from the second node head = head.next; // While there are nodes in linked list while (head != null) { // max_ending_here will be the maximum of either // the current node's value or the current node's // value added with the max_ending_here // for the previous node max_ending_here = Math.max(head.data, max_ending_here + head.data); // Update the maximum sum so far max_so_far = Math.max(max_ending_here, max_so_far); // Get to the next node head = head.next; } // Return the maximum sum so far return max_so_far;}// Driver codepublic static void main(String[] args){ // Create the linked list Node head = null; head = append(head, -2); head = append(head, -3); head = append(head, 4); head = append(head, -1); head = append(head, -2); head = append(head, 1); head = append(head, 5); head = append(head, -3); System.out.print(MaxContiguousNodeSum(head));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach # A linked list nodeclass Node: def __init__(self, data): self.data = data self.next = None # Given a reference (pointer to pointer) # to the head of a list and an int, # appends a new node at the end def append(head_ref, new_data): # Allocate node new_node = Node(new_data) last = head_ref # used in step 5 # This new node is going to be # the last node, so make next of # it as None new_node.next = None # If the Linked List is empty, # then make the new node as head if (head_ref == None): head_ref = new_node return head_ref # Else traverse till the last node while (last.next != None): last = last.next # Change the next of last node last.next = new_node return head_ref# Function to return the maximum contiguous# nodes sum in the given linked listdef MaxContiguousNodeSum(head): # If the list is empty if (head == None): return 0 # If the list contains a single element if (head.next == None): return head.data # max_ending_here will store the maximum # sum ending at the current node, currently # it will be initialised to the maximum # sum ending at the first node which is # the first node's value max_ending_here = head.data # max_so_far will store the maximum sum of # contiguous nodes so far which is the required # answer at the end of the linked list traversal max_so_far = head.data # Starting from the second node head = head.next # While there are nodes in linked list while (head != None): # max_ending_here will be the maximum of either # the current node's value or the current node's # value added with the max_ending_here # for the previous node max_ending_here = max(head.data, max_ending_here + head.data) # Update the maximum sum so far max_so_far = max(max_ending_here, max_so_far) # Get to the next node head = head.next # Return the maximum sum so far return max_so_far # Driver codeif __name__=='__main__': # Create the linked list head = None head = append(head, -2) head = append(head, -3) head = append(head, 4) head = append(head, -1) head = append(head, -2) head = append(head, 1) head = append(head, 5) head = append(head, -3) print(MaxContiguousNodeSum(head))# This code is contributed by rutvik_56 |
C#
// C# implementation of the approachusing System;class GFG{// A linked list nodepublic class Node { public int data; public Node next;};/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */static Node append(Node head_ref, int new_data){ // Allocate node Node new_node = new Node(); Node last = head_ref; /* used in step 5*/ // Put in the data new_node.data = new_data; /* This new node is going to be the last node, so make next of it as null*/ new_node.next = null; /* If the Linked List is empty, then make the new node as head */ if (head_ref == null) { head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; return head_ref;}// Function to return the maximum contiguous// nodes sum in the given linked liststatic int MaxContiguousNodeSum(Node head){ // If the list is empty if (head == null) return 0; // If the list contains a single element if (head.next == null) return head.data; // max_ending_here will store the maximum sum // ending at the current node, currently it // will be initialised to the maximum sum ending // at the first node which is the first node's value int max_ending_here = head.data; // max_so_far will store the maximum sum of // contiguous nodes so far which is the required // answer at the end of the linked list traversal int max_so_far = head.data; // Starting from the second node head = head.next; // While there are nodes in linked list while (head != null) { // max_ending_here will be the maximum of either // the current node's value or the current node's // value added with the max_ending_here // for the previous node max_ending_here = Math.Max(head.data, max_ending_here + head.data); // Update the maximum sum so far max_so_far = Math.Max(max_ending_here, max_so_far); // Get to the next node head = head.next; } // Return the maximum sum so far return max_so_far;}// Driver codepublic static void Main(String[] args){ // Create the linked list Node head = null; head = append(head, -2); head = append(head, -3); head = append(head, 4); head = append(head, -1); head = append(head, -2); head = append(head, 1); head = append(head, 5); head = append(head, -3); Console.Write(MaxContiguousNodeSum(head));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach// Structure of a node of the linked listclass Node { constructor() { this.data = 0; this.next = null; }}/* Given a reference (pointer to pointer) to the headof a list and an int, appends a new node at the end */function append( head_ref, new_data){ // Allocate node var new_node = new Node(); var last = head_ref; /* used in step 5*/ // Put in the data new_node.data = new_data; /* This new node is going to be the last node, so make next of it as null*/ new_node.next = null; /* If the Linked List is empty, then make the new node as head */ if (head_ref == null) { head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; return head_ref;}// Function to return the maximum contiguous// nodes sum in the given linked listfunction MaxContiguousNodeSum( head){ // If the list is empty if (head == null) return 0; // If the list contains a single element if (head.next == null) return head.data; // max_ending_here will store the maximum sum // ending at the current node, currently it // will be initialised to the maximum sum ending // at the first node which is the first node's value let max_ending_here = head.data; // max_so_far will store the maximum sum of // contiguous nodes so far which is the required // answer at the end of the linked list traversal let max_so_far = head.data; // Starting from the second node head = head.next; // While there are nodes in linked list while (head != null) { // max_ending_here will be the maximum of either // the current node's value or the current node's // value added with the max_ending_here // for the previous node max_ending_here = Math.max(head.data, max_ending_here + head.data); // Update the maximum sum so far max_so_far = Math.max(max_ending_here, max_so_far); // Get to the next node head = head.next; } // Return the maximum sum so far return max_so_far;}// Driver Code// Create the linked listvar head = null;head = append(head, -2);head = append(head, -3);head = append(head, 4);head = append(head, -1);head = append(head, -2);head = append(head, 1);head = append(head, 5);head = append(head, -3);document.write(MaxContiguousNodeSum(head)); </script> |
Output:
7
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
