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