Dada una lista enlazada, la tarea es encontrar la suma máxima obtenida al sumar cualquier k Nodes consecutivos de la lista enlazada.
Ejemplos:
Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL, K = 5
Salida: 20
La suma máxima se obtiene sumando los últimos 5 NodesEntrada: 2 -> 5 -> 3 -> 6 -> 4 -> 1 -> 7 -> NULO, K = 4
Salida: 18
Enfoque: la idea es usar una ventana deslizante de tamaño k, realizar un seguimiento de la suma de la ventana actual y actualizar la suma máxima si es necesario. Para implementar la ventana deslizante, se pueden usar dos punteros para representar el punto inicial y final. En cada paso, primero, el valor del Node apuntado por el inicio se resta de la suma actual y el valor del Node apuntado por el final se suma a la suma actual. Esta suma se compara con la suma máxima y el resultado se actualiza si es necesario. Los punteros de inicio y final se incrementan en uno en cada paso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
struct Node {
int data;
Node* next;
};
// Function to create new node
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 nodes
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 = max(maxSum, sum);
}
return maxSum;
}
// Driver code
int 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 approach
class GFG
{
// Structure of a node
static class Node
{
int data;
Node next;
};
// Function to create new node
static 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 nodes
static 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 code
public 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 List class Node: def __init__(self, x): self.data = x self.next = None # Function to return the maximum sum of # k consecutive nodes def 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 code if __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 approach
using System;
class GFG
{
// Structure of a node
public class Node
{
public int data;
public Node next;
};
// Function to create new node
static 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 nodes
static 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 code
public 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 node
class 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>
Producción:
20
Complejidad temporal: O(n)
Espacio auxiliar: O(1)