Рубрики

Максимальная сумма подмассива такая, что начальное и конечное значения совпадают

Для заданного массива из N положительных чисел задача состоит в том, чтобы найти смежный подрешетку (LR) такой, что a [L] = a [R] и сумма a [L] + a [L + 1] +… + a [R ] это максимум.

Примеры:

Input: arr[] = {1, 3, 2, 2, 3}
Output: 10
Subarray [3, 2, 2, 3] starts and ends with 3 and has sum = 10

Input: arr[] = {1, 3, 2, 2, 3}
Output: 10

Подход: для каждого элемента в массиве найдем 2 значения: первое (крайнее левое) вхождение в массив и последнее (крайнее правое) вхождение в массив. Поскольку все числа положительны, увеличение количества слагаемых может только увеличить сумму. Следовательно, для каждого числа в массиве мы находим сумму между самым левым и самым правым вхождением, что можно быстро сделать, используя префиксные суммы. Мы можем отслеживать максимальное найденное значение и распечатать его в конце.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска максимальной суммы

int maxValue(int a[], int n)

{

    unordered_map<int, int> first, last;

    int pr[n];

    pr[0] = a[0];

  

    for (int i = 1; i < n; i++) {

  

        // Создание массива префиксных сумм

        pr[i] = pr[i - 1] + a[i];

  

        // Если значение не встречалось раньше,

        // Это первое вхождение

        if (first[a[i]] == 0)

            first[a[i]] = i;

  

        // Продолжаем обновлять последнее вхождение

        last[a[i]] = i;

    }

  

    int ans = 0;

  

    // Находим максимальную сумму с одинаковыми первым и последним значением

    for (int i = 0; i < n; i++) {

        int start = first[a[i]];

        int end = last[a[i]];

        ans = max(ans, pr[end] - pr[start - 1]);

    }

    return ans;

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 3, 5, 2, 4, 18, 2, 3 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << maxValue(arr, n);

  

    return 0;

}

Джава

// Java реализация вышеуказанного подхода

import java.io.*;

import java.util.*;

  

class GFG {

  

    // Функция для поиска максимальной суммы

    static int maxValue(int a[], int n)

    {

        HashMap<Integer, Integer> first = new HashMap<>();

        HashMap<Integer, Integer> last = new HashMap<>();

        for (int i = 0; i < n; i++) {

            first.put(a[i], 0);

            last.put(a[i], 0);

        }

  

        int[] pr = new int[n];

        pr[0] = a[0];

  

        for (int i = 1; i < n; i++) {

  

            // Создание массива префиксных сумм

            pr[i] = pr[i - 1] + a[i];

  

            // Если значение не встречалось раньше,

            // Это первое вхождение

            if (Integer.parseInt(String.valueOf(first.get(a[i]))) == 0)

                first.put(a[i], i);

  

            // Продолжаем обновлять последнее вхождение

            last.put(a[i], i);

        }

  

        int ans = 0;

  

        // Находим максимальную сумму с одинаковыми первым и последним значением

        for (int i = 0; i < n; i++) {

            int start = Integer.parseInt(String.valueOf(first.get(a[i])));

            int end = Integer.parseInt(String.valueOf(last.get(a[i])));

            if (start != 0)

                ans = Math.max(ans, pr[end] - pr[start - 1]);

        }

  

        return ans;

    }

  

    // Код драйвера

    public static void main(String args[])

    {

        int[] arr = { 1, 3, 5, 2, 4, 18, 2, 3 };

        int n = arr.length;

        System.out.print(maxValue(arr, n));

    }

}

  
// Этот код предоставлен rachana soma

python3

# Python3 реализация вышеуказанного подхода

from collections import defaultdict

  
# Функция поиска максимальной суммы

def maxValue(a, n): 

   

    first = defaultdict(lambda:0)

    last = defaultdict(lambda:0)

      

    pr = [None] *

    pr[0] = a[0

    

    for i in range(1, n):  

    

        # Построить массив сумм префиксов

        pr[i] = pr[i - 1] + a[i] 

    

        # Если значение не встречалось раньше,

        # Это первое вхождение

        if first[a[i]] == 0

            first[a[i]] =

    

        # Продолжайте обновлять последнее вхождение

        last[a[i]] =

       

    

    ans = 0 

    

    # Найти максимальную сумму с одинаковыми первым и последним значением

    for i in range(0, n):  

        start = first[a[i]] 

        end = last[a[i]] 

        ans = max(ans, pr[end] - pr[start - 1]) 

       

    return ans 

   

    
Код водителя

if __name__ == "__main__"

   

    arr =  [1, 3, 5, 2, 4, 18, 2, 3]  

    n = len(arr) 

    

    print(maxValue(arr, n)) 

    
# Этот код предоставлен Rituraj Jain

C #

// C # реализация вышеуказанного подхода

using System;

using System.Collections.Generic;

  

class GFG 

{

  

    // Функция для поиска максимальной суммы

    static int maxValue(int []a, int n)

    {

        Dictionary<int

                   int> first = new Dictionary<int

                                               int>();

        Dictionary<int

                   int> last = new Dictionary<int,  

                                              int>();

          

        for (int i = 0; i < n; i++) 

        {

            first[a[i]] = 0;

            last[a[i]] = 0;

        }

  

        int[] pr = new int[n];

        pr[0] = a[0];

  

        for (int i = 1; i < n; i++) 

        {

  

            // Создание массива префиксных сумм

            pr[i] = pr[i - 1] + a[i];

  

            // Если значение не встречалось раньше,

            // Это первое вхождение

            if (first[a[i]] == 0)

                first[a[i]] = i;

  

            // Продолжаем обновлять последнее вхождение

            last[a[i]] = i;

        }

  

        int ans = 0;

  

        // Находим максимальную сумму с

        // одно и то же первое и последнее значение

        for (int i = 0; i < n; i++) 

        {

            int start = first[a[i]];

            int end = last[a[i]];

            if (start != 0)

                ans = Math.Max(ans, pr[end] - pr[start - 1]);

        }

        return ans;

    }

  

    // Код драйвера

    static void Main()

    {

        int[] arr = { 1, 3, 5, 2, 4, 18, 2, 3 };

        int n = arr.Length;

        Console.Write(maxValue(arr, n));

    }

}

  
// Этот код предоставлен Мохит Кумар

Выход:

37

Сложность времени: O (N)

Рекомендуемые посты:

Максимальная сумма подмассива такая, что начальное и конечное значения совпадают

0.00 (0%) 0 votes