# Sum of minimum element of all subarrays of a sorted array

Given a sorted array **A** of **n** integers. The task is to find the sum of the minimum of all possible subarrays of **A**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:A = [ 1, 2, 4, 5]Output:23

Subsequences are [1], [2], [4], [5], [1, 2], [2, 4], [4, 5] [1, 2, 4], [2, 4, 5], [1, 2, 4, 5]

Minimums are 1, 2, 4, 5, 1, 2, 4, 1, 2, 1.

Sum is 23Input:A = [1, 2, 3]Output:10

**Approach:** The Naive approach is to generate all possible subarrays, find their minimum and add them to the result. **Efficient Approach:** It is given that the array is sorted, so observe that the minimum element occurs N times, the second minimum occurs N-1 times, and so on… Let’s take an example:

arr[] = {1, 2, 3}

Subarrays are {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}

Minimum of each subarray: {1}, {2}, {3}, {1}, {2}, {1}.

where

1 occurs 3 times i.e. n times when n = 3.

2 occurs 2 times i.e. n-1 times when n = 3.

3 occurs 1 times i.e. n-2 times when n = 3.

So, traverse the array and add the current element i.e. (arr[i]* n-i) to the sum.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the sum` `// of minimum of all subarrays` `int` `findMinSum(` `int` `arr[], ` `int` `n)` `{` ` ` `int` `sum = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `sum += arr[i] * (n - i);` ` ` `return` `sum;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `arr[] = { 3, 5, 7, 8 };` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << findMinSum(arr, n);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the above approach` `class` `GfG` `{` `// Function to find the sum` `// of minimum of all subarrays` `static` `int` `findMinSum(` `int` `arr[], ` `int` `n)` `{` ` ` `int` `sum = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++)` ` ` `sum += arr[i] * (n - i);` ` ` `return` `sum;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `arr[] = { ` `3` `, ` `5` `, ` `7` `, ` `8` `};` ` ` `int` `n = arr.length;` ` ` `System.out.println(findMinSum(arr, n));` `}` `}` `// This code is contributed by Prerna Saini` |

## Python3

`# Python3 implementation of the` `# above approach` `# Function to find the sum` `# of minimum of all subarrays` `def` `findMinSum(arr, n):` ` ` `sum` `=` `0` ` ` `for` `i ` `in` `range` `(` `0` `, n):` ` ` `sum` `+` `=` `arr[i] ` `*` `(n ` `-` `i)` ` ` `return` `sum` `# Driver code` `arr ` `=` `[` `3` `, ` `5` `, ` `7` `, ` `8` `]` `n ` `=` `len` `(arr)` `print` `(findMinSum(arr, n))` `# This code has been contributed` `# by 29AjayKumar` |

## C#

`// C# implementation of the above approach` `using` `System;` `class` `GfG` `{` `// Function to find the sum` `// of minimum of all subarrays` `static` `int` `findMinSum(` `int` `[]arr, ` `int` `n)` `{` ` ` `int` `sum = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `sum += arr[i] * (n - i);` ` ` `return` `sum;` `}` `// Driver code` `public` `static` `void` `Main(String []args)` `{` ` ` `int` `[]arr = { 3, 5, 7, 8 };` ` ` `int` `n = arr.Length;` ` ` `Console.WriteLine(findMinSum(arr, n));` `}` `}` `// This code is contributed by Arnab Kundu` |

## PHP

`<?php` `// PHP implementation of the above approach` `// Function to find the sum` `// of minimum of all subarrays` `function` `findMinSum(` `$arr` `,` `$n` `)` `{` ` ` `$sum` `= 0;` ` ` `for` `(` `$i` `= 0; ` `$i` `< ` `$n` `; ` `$i` `++)` ` ` `$sum` `+= ` `$arr` `[` `$i` `] * (` `$n` `- ` `$i` `);` ` ` `return` `$sum` `;` `}` `// Driver code` `$arr` `= ` `array` `( 3, 5, 7, 8 );` `$n` `= ` `count` `(` `$arr` `);` `echo` `findMinSum(` `$arr` `, ` `$n` `);` ` ` `// This code is contributed by Arnab Kundu` `?>` |

## Javascript

`<script>` `// Javascript implementation of the above approach` `// Function to find the sum` `// of minimum of all subarrays` `function` `findMinSum(arr, n)` `{` ` ` `var` `sum = 0;` ` ` `for` `(` `var` `i = 0; i < n; i++)` ` ` `sum += arr[i] * (n - i);` ` ` `return` `sum;` `}` `// Driver code` `var` `arr = [ 3, 5, 7, 8 ];` `var` `n = arr.length;` `document.write( findMinSum(arr, n));` `</script>` |

**Output:**

49

**Note:** To find the **Sum of maximum element of all subarrays in a sorted array**, just traverse the array in reverse order and apply the same formula for Sum.