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

Опубликовано: 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 minimum elements is 1 + 2 + 3 + 1 + 2 + 1 = 10
Input: arr[] = {3, 1} 
Output: 5  

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

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

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

Следующая идея, которая может прийти нам в голову, будет для каждого индекса 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)

The Best method: 
This problem can be solved using a stack data structure in O(n) time. The idea remains the same as is in the previous approach. For the sake of saving some time, we will use a stack from the Standard Template Library of C++.
Left count: Let CLi represent the left count for an index i. CLi for an index i can be defined as the number of elements between the index i and the right most element whose value is strictly less than arr[i] having index less than i. If, there is no such element, then CLi for an element will be equal to the number of elements to the left of the index i
To achieve this, we will insert only the index of the elements from left to right into the stack. Let us suppose, we are inserting an index i in the stack and j be the index of the topmost element currently present in the stack. While the value arr[i] is less than or equal to the value at the topmost index in the stack and the stack is not empty, keep popping the elements in the stack. Whenever, an element is popped, the left count(CLi) of the current index(i) is updated as CLi = CLi + CLj + 1.
Right count: We calculate the right count for all the indexes similarly. The only difference is we push the elements in the stack while traversing right to left in the array. While arr[i] is strictly less than the value at the topmost index in the stack and the stack is not empty, keep popping the elements. Whenever, an element is popped, the right count of the current index(i) is updated as CRi = CRi + CRj + 1.
Final step: Let ans be the variable containing the final answer. We will initialize it with 0. Then, we will iterate through all the indexes from 1 to n of the array and update the ans as ans = ans + (CLi + 1) * (CRi + 1) * arr[i] for all possible values of i from 1 to n.
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 findMinSum(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 << findMinSum(arr, n);
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
// Function to return the required sum
static int findMinSum(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(findMinSum(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

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 findMinSum(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(findMinSum(arr, n));
}
}
 
// This code has been contributed
// by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
 
// Function to return the required sum
function findMinSum(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( findMinSum(arr, n));
 
 
 
</script>
Output: 
10

 

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

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ