Сумма максимальных элементов всех возможных подмассивов массива

Опубликовано: 14 Января, 2022

Для данного массива arr [] задача состоит в том, чтобы найти сумму максимальных элементов каждого возможного подмассива массива.

Примеры:

Input: arr[] = {1, 3, 2} 
Output: 15 
All possible sub-arrays are {1}, {2}, {3}, {1, 3}, {3, 2} and {1, 3, 2} 
And, the sum of all the maximum elements is 1 + 2 + 3 + 3 + 3 + 3 = 15
Input: arr[] = {3, 1} 
Output: 7  

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простой метод - сгенерировать все подмассивы, а затем просуммировать максимальное количество элементов во всех из них. Временная сложность этого решения будет O (n 3 ).

Лучший метод:
Ключ к оптимизации - это вопрос -

In how many segments, the value at an index will be maximum?

Следующая идея, которая может прийти нам в голову, будет для каждого индекса i в массиве arr , который мы попытаемся найти:
Счетчик слева: мы выполняем итерацию слева от индекса i до тех пор, пока не встретим элемент, строго превышающий arr [i], или не дойдем до левого конца массива. Назовем этот счетчик для индекса i данного массива CLi .
Правильный счет: мы выполняем итерацию вправо от индекса до тех пор, пока не встретим элемент, больший или равный значению в индексе, или мы не дойдем до правого конца. Назовем этот счетчик для индекса i данного массива CRi .
(CLi + 1) * (CRi + 1) будет количеством подмассивов для текущего индекса i, в котором его значение будет максимальным, потому что есть способы CLi + 1 для выбора элементов с левой стороны (включая отсутствие выбора элемента ) и CRi + 1 способы выбора элементов с правой стороны.

The time complexity of this approach will be O(n2)

Лучший способ:
Эта проблема может быть решена с использованием структуры данных стека за время O (n) . Идея остается такой же, как и в предыдущем подходе. Для экономии времени воспользуемся стеком из стандартной библиотеки шаблонов C ++.
Счетчик слева: пусть CLi представляет счетчик слева для индекса i . CLi для индекса i можно определить как количество элементов между индексом i и крайним правым элементом, значение которого строго больше, чем arr [i], имеющего индекс меньше i . Если такого элемента нет, то CLi для элемента будет равно количеству элементов слева от индекса i .
Для этого мы вставим в стек только индекс элементов слева направо. Предположим, мы вставляем индекс i в стек, а j будет индексом самого верхнего элемента, присутствующего в данный момент в стеке. Пока значение arr [i] больше или равно значению в самом верхнем индексе в стеке и стек не пуст, продолжайте выталкивать элементы в стек. Каждый раз, когда элемент выталкивается, счетчик слева (CLi) текущего индекса (i) обновляется как CLi = CLi + CLj + 1 .
Правильный счет: мы рассчитываем правильный счет для всех индексов одинаково. Единственная разница в том, что мы проталкиваем элементы в стек, перемещаясь по массиву справа налево. Хотя arr [i] строго больше, чем значение в самом верхнем индексе в стеке, а стек не пуст, продолжайте выталкивать элементы. Всякий раз, когда элемент выталкивается, правильный счет текущего индекса (i) обновляется как CRi = CRi + CRj + 1 .
Последний шаг: пусть ans будет переменной, содержащей окончательный ответ. Мы инициализируем его 0 . Затем мы переберем все индексы от 1 до n массива и обновим ans как ans = ans + (CLi + 1) * (CRi + 1) * arr [i] для всех возможных значений i от 1 до п .

Below is the implementation of the above approach: 

C++

// C++ implementation of the approach
#include <iostream>
#include <stack>
using namespace std;
 
// Function to return the required sum
int findMaxSum(int arr[], int n)
{
    // Arrays for maintaining left and right count
    int CL[n] = { 0 }, CR[n] = { 0 };
 
    // Stack for storing the indexes
    stack<int> q;
 
    // Calculate left count for every index
    for (int i = 0; i < n; i++) {
        while (q.size() != 0 && arr[q.top()] <= arr[i]) {
            CL[i] += CL[q.top()] + 1;
            q.pop();
        }
        q.push(i);
    }
 
    // Clear the stack
    while (q.size() != 0)
        q.pop();
 
    // Calculate right count for every index
    for (int i = n - 1; i >= 0; i--) {
        while (q.size() != 0 && arr[q.top()] < arr[i]) {
            CR[i] += CR[q.top()] + 1;
            q.pop();
        }
        q.push(i);
    }
 
    // Clear the stack
    while (q.size() != 0)
        q.pop();
 
    // To store the required sum
    int ans = 0;
 
    // Calculate the final sum
    for (int i = 0; i < n; i++)
        ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findMaxSum(arr, n);
}

Java

// Java implementation of the above approach
import java.util.*;
 
public class GFG
{
    // Function to return the required sum
    static int findMaxSum(int arr[], int n)
    {
        // Arrays for maintaining left and right count
        int CL[] = new int[n], CR[] = new int[n];
     
        // Stack for storing the indexes
        Stack<Integer> q = new Stack<Integer>();
     
        // Calculate left count for every index
        for (int i = 0; i < n; i++)
        {
            while (q.size() != 0 && arr[q.peek()] <= arr[i])
            {
                CL[i] += CL[q.peek()] + 1;
                q.pop();
            }
            q.push(i);
        }
     
        // Clear the stack
        while (q.size() != 0)
            q.pop();
     
        // Calculate right count for every index
        for (int i = n - 1; i >= 0; i--)
        {
            while (q.size() != 0 && arr[q.peek()] < arr[i])
            {
                CR[i] += CR[q.peek()] + 1;
                q.pop();
            }
            q.push(i);
        }
     
        // Clear the stack
        while (q.size() != 0)
            q.pop();
     
        // To store the required sum
        int ans = 0;
     
        // Calculate the final sum
        for (int i = 0; i < n; i++)
            ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
     
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 2 };
        int n = arr.length;
        System.out.println(findMaxSum(arr, n));
    }
}
 
// This code is contributed by Rituraj Jain

Python3

# Python3 implementation of the approach
 
# Function to return the required sum
def findMinSum(arr, n):
 
    # Arrays for maintaining left
    # and right count
    CL = [0] * n
    CR = [0] * n
 
    # Stack for storing the indexes
    q = []
 
    # Calculate left count for every index
    for i in range(0, n):
        while (len(q) != 0 and
               arr[q[-1]] <= arr[i]):
            CL[i] += CL[q[-1]] + 1
            q.pop()
         
        q.append(i)
 
    # Clear the stack
    while len(q) != 0:
        q.pop()
 
    # Calculate right count for every index
    for i in range(n - 1, -1, -1):
        while (len(q) != 0 and
               arr[q[-1]] < arr[i]):
            CR[i] += CR[q[-1]] + 1
            q.pop()
         
        q.append(i)
 
    # Clear the stack
    while len(q) != 0:
        q.pop()
 
    # To store the required sum
    ans = 0
 
    # Calculate the final sum
    for i in range(0, n):
        ans += (CL[i] + 1) * (CR[i] + 1) * arr[i]
 
    return ans
 
# Driver code
if __name__ == "__main__":
 
    arr = [1, 3, 2]
    n = len(arr)
    print(findMinSum(arr, n))
     
# This code is contributed by Rituraj Jain

C#

// C# implementation of the above approach
using System;
using System.Collections.Generic;
     
class GFG
{
    // Function to return the required sum
    static int findMaxSum(int []arr, int n)
    {
        // Arrays for maintaining left and right count
        int []CL = new int[n]; int []CR = new int[n];
     
        // Stack for storing the indexes
        Stack<int> q = new Stack<int>();
     
        // Calculate left count for every index
        for (int i = 0; i < n; i++)
        {
            while (q.Count != 0 && arr[q.Peek()] <= arr[i])
            {
                CL[i] += CL[q.Peek()] + 1;
                q.Pop();
            }
            q.Push(i);
        }
     
        // Clear the stack
        while (q.Count != 0)
            q.Pop();
     
        // Calculate right count for every index
        for (int i = n - 1; i >= 0; i--)
        {
            while (q.Count != 0 && arr[q.Peek()] < arr[i])
            {
                CR[i] += CR[q.Peek()] + 1;
                q.Pop();
            }
            q.Push(i);
        }
     
        // Clear the stack
        while (q.Count != 0)
            q.Pop();
     
        // To store the required sum
        int ans = 0;
     
        // Calculate the final sum
        for (int i = 0; i < n; i++)
            ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
     
        return ans;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []arr = { 1, 3, 2 };
        int n = arr.Length;
        Console.WriteLine(findMaxSum(arr, n));
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the required sum
function findMaxSum(arr, n)
{
    // Arrays for maintaining left and right count
    var CL = Array(n).fill(0);
    var CR = Array(n).fill(0);
 
    // Stack for storing the indexes
    var q = [];
 
    // Calculate left count for every index
    for (var i = 0; i < n; i++) {
        while (q.length != 0 && arr[q[q.length-1]] <= arr[i]) {
            CL[i] += CL[q[q.length-1]] + 1;
            q.pop();
        }
        q.push(i);
    }
 
    // Clear the stack
    while (q.length != 0)
        q.pop();
 
    // Calculate right count for every index
    for (var i = n - 1; i >= 0; i--) {
        while (q.length != 0 && arr[q[q.length-1]] < arr[i]) {
            CR[i] += CR[q[q.length-1]] + 1;
            q.pop();
        }
        q.push(i);
    }
 
    // Clear the stack
    while (q.length != 0)
        q.pop();
 
    // To store the required sum
    var ans = 0;
 
    // Calculate the final sum
    for (var i = 0; i < n; i++)
        ans += (CL[i] + 1) * (CR[i] + 1) * arr[i];
 
    return ans;
}
 
// Driver code
var arr = [1, 3, 2];
var n = arr.length;
document.write( findMaxSum(arr, n));
 
</script>
Output: 
15

 

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

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.