Given a linked list, the task is to find the maximum sum obtained by adding any k consecutive nodes of linked list.
Examples:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL, K = 5
Output: 20
Maximum sum is obtained by adding last 5 nodesInput: 2 -> 5 -> 3 -> 6 -> 4 -> 1 -> 7 -> NULL, K = 4
Output: 18
Approach: The idea is to use a sliding window of size k, keep track of sum of current window and update maximum sum if required. To implement sliding window two pointers can be used to represent starting and ending point. At each step first the value of node pointed by start is subtracted from current sum and the value of node pointed by end is added to current sum. This sum is compared to maximum sum and result is updated if required. The start and end pointers are incremented by one at each step.
Below is the implementation of above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Structure of a nodestruct Node { int data; Node* next;};// Function to create new nodeNode* newNode(int data){ Node* node = new Node; node->next = NULL; node->data = data; return node;}// Function to return the maximum sum of// k consecutive nodesint findMaxSum(Node* head, int k){ // To store current window sum int sum = 0; // To store maximum sum int maxSum = 0; // Pointer to the start of window Node* start = head; // Pointer to the end of window Node* end = head; int i; // Find the sum of first k nodes for (i = 0; i < k; i++) { sum += end->data; end = end->next; } maxSum = sum; // Move window by one step and // update sum. Node pointed by // start is excluded from current // window so subtract it. Node // pointed by end is added to // current window so add its value. while (end != NULL) { // Subtract the starting element // from previous window sum -= start->data; start = start->next; // Add the element next to the end // of previous window sum += end->data; end = end->next; // Update the maximum sum so far maxSum = max(maxSum, sum); } return maxSum;}// Driver codeint main(){ Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); head->next->next->next->next = newNode(5); head->next->next->next->next->next = newNode(6); int k = 5; cout << findMaxSum(head, k); return 0;} |
Java
// Java implementation of the approachclass GFG{// Structure of a nodestatic class Node{ int data; Node next;};// Function to create new nodestatic Node newNode(int data){ Node node = new Node(); node.next = null; node.data = data; return node;}// Function to return the maximum sum of// k consecutive nodesstatic int findMaxSum(Node head, int k){ // To store current window sum int sum = 0; // To store maximum sum int maxSum = 0; // Pointer to the start of window Node start = head; // Pointer to the end of window Node end = head; int i; // Find the sum of first k nodes for (i = 0; i < k; i++) { sum += end.data; end = end.next; } maxSum = sum; // Move window by one step and // update sum. Node pointed by // start is excluded from current // window so subtract it. Node // pointed by end is added to // current window so add its value. while (end != null) { // Subtract the starting element // from previous window sum -= start.data; start = start.next; // Add the element next to the end // of previous window sum += end.data; end = end.next; // Update the maximum sum so far maxSum = Math.max(maxSum, sum); } return maxSum;}// Driver codepublic static void main(String[] args){ Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); head.next.next.next.next = newNode(5); head.next.next.next.next.next = newNode(6); int k = 5; System.out.print(findMaxSum(head, k));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach # Node of Linked Listclass Node: def __init__(self, x): self.data = x self.next = None# Function to return the maximum sum of# k consecutive nodesdef findMaxSum(head, k): # To store current window sum sum = 0 # To store maximum sum maxSum = 0 # Pointer to the start of window start = head # Pointer to the end of window end = head # Find the sum of first k nodes for i in range(k): sum += end.data end = end.next maxSum = sum # Move window by one step and # update sum. Node pointed by # start is excluded from current # window so subtract it. Node # pointed by end is added to # current window so add its value. while (end != None): # Subtract the starting element # from previous window sum -= start.data start = start.next # Add the element next to the end # of previous window sum += end.data end = end.next # Update the maximum sum so far maxSum = max(maxSum, sum) return maxSum# Driver codeif __name__ == '__main__': head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(6) k = 5 print(findMaxSum(head, k))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;class GFG{// Structure of a nodepublic class Node{ public int data; public Node next;};// Function to create new nodestatic Node newNode(int data){ Node node = new Node(); node.next = null; node.data = data; return node;}// Function to return the maximum sum of// k consecutive nodesstatic int findMaxSum(Node head, int k){ // To store current window sum int sum = 0; // To store maximum sum int maxSum = 0; // Pointer to the start of window Node start = head; // Pointer to the end of window Node end = head; int i; // Find the sum of first k nodes for (i = 0; i < k; i++) { sum += end.data; end = end.next; } maxSum = sum; // Move window by one step and // update sum. Node pointed by // start is excluded from current // window so subtract it. Node // pointed by end is added to // current window so add its value. while (end != null) { // Subtract the starting element // from previous window sum -= start.data; start = start.next; // Add the element next to the end // of previous window sum += end.data; end = end.next; // Update the maximum sum so far maxSum = Math.Max(maxSum, sum); } return maxSum;}// Driver codepublic static void Main(String[] args){ Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); head.next.next.next.next = newNode(5); head.next.next.next.next.next = newNode(6); int k = 5; Console.Write(findMaxSum(head, k));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the approach // Structure of a nodeclass Node { constructor(val) { this.data = val; this.next = null; }} // Function to create new node function newNode(data) { var node = new Node(); node.next = null; node.data = data; return node; } // Function to return the maximum sum of // k consecutive nodes function findMaxSum(head , k) { // To store current window sum var sum = 0; // To store maximum sum var maxSum = 0; // Pointer to the start of window var start = head; // Pointer to the end of window var end = head; var i; // Find the sum of first k nodes for (i = 0; i < k; i++) { sum += end.data; end = end.next; } maxSum = sum; // Move window by one step and // update sum. Node pointed by // start is excluded from current // window so subtract it. Node // pointed by end is added to // current window so add its value. while (end != null) { // Subtract the starting element // from previous window sum -= start.data; start = start.next; // Add the element next to the end // of previous window sum += end.data; end = end.next; // Update the maximum sum so far maxSum = Math.max(maxSum, sum); } return maxSum; } // Driver code var head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); head.next.next.next.next = newNode(5); head.next.next.next.next.next = newNode(6); var k = 5; document.write(findMaxSum(head, k));// This code contributed by aashish1995</script> |
Output:
20
Time Complexity: O(n)
Auxiliary Space: O(1)
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!
