Максимальная сумма K последовательных узлов в данном связанном списке
Учитывая связанный список, задача состоит в том, чтобы найти максимальную сумму, полученную путем добавления любых k последовательных узлов связанного списка.
Примеры:
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
Подход: идея состоит в том, чтобы использовать скользящее окно размера k, отслеживать сумму текущего окна и при необходимости обновлять максимальную сумму. Для реализации скользящего окна можно использовать два указателя для обозначения начальной и конечной точки. На каждом шаге сначала значение узла, указанного параметром start, вычитается из текущей суммы, а значение узла, указанного параметром end, добавляется к текущей сумме. Эта сумма сравнивается с максимальной суммой, и результат при необходимости обновляется. Указатели начала и конца увеличиваются на единицу на каждом шаге.
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 |
20
Сложность времени: O (n)
Вспомогательное пространство: O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.