Dada una lista enlazada, la tarea es encontrar la suma máxima para cualquier Node contiguo.
Ejemplos:
Entrada: -2 -> -3 -> 4 -> -1 -> -2 -> 1 -> 5 -> -3 -> NULL
Salida: 7
4 -> -1 -> -2 -> 1 -> 5 es la sublista con la suma dada.Entrada: 1 -> 2 -> 3 -> 4 -> NULO
Salida: 10
Enfoque: el algoritmo de Kadane se ha discutido en este artículo para trabajar en arrays para encontrar la suma máxima de sub-arrays, pero también se puede modificar para que funcione en listas enlazadas. Dado que el algoritmo de Kadane no requiere acceder a elementos aleatorios, también es aplicable en las listas enlazadas en tiempo lineal.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class 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 list
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 = 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 code
int 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 approach
class GFG
{
// A linked list node
static 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 list
static 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 code
public 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 node class 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 list def 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 code if __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 approach
using System;
class GFG
{
// A linked list node
public 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 list
static 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 code
public 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 list
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/* Given a reference (pointer to pointer) to the head
of 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 list
function 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 list
var 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>
Producción:
7