Sum of absolute difference of maximum and minimum of all subarrays
Given an array arr containing N integers, the task is to find the sum of the absolute difference of maximum and minimum of all subarrays.
Example:
Input: arr[] = {1, 4, 3}
Output: 7
Explanation: The following are the six subarrays:
[1] : maximum – minimum= 1 – 1 = 0
[4] : maximum – minimum= 4 – 4 = 0
[3] : maximum – minimum= 3 – 3 = 0
[1, 4] : maximum – minimum= 4 – 1 = 3
[4, 3] : maximum – minimum= 4 – 3 = 1
[1, 4, 3] : maximum – minimum= 4 – 1 = 3
As a result, the total sum is: 0 + 0 + 0 + 3 + 1 + 3 = 7Input: arr[] = {1, 6, 3}
Output: 13
Approach: The approach is to find all possible subarrays, and maintain their maximum and minimum, then use them to calculate the sum. Now, follow the below step to solve this problem:
- Create a variable sum to store the final answer and initialise it to 0.
- Run a loop from i=0 to i<N and in each iteration:
- Create two variables mx and mn to store the maximum and minimum of the subarray respectively.
- Initialise mx and mn to arr[i].
- Now, run another loop from j=i to j<N:
- Each iteration of this loop is used to calculate the maximum and minimum of subarray from i to j.
- So, change mx to the maximum out of mx and arr[j].
- And change mn to the minimum of mn and arr[j].
- Now, add (mx-mn) to the sum.
- Return sum as the final answer to this problem.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the sum // of the absolute difference // of maximum and minimum of all subarrays int sumOfDiff(vector< int >& arr) { int sum = 0; int n = arr.size(); for ( int i = 0; i < n; i++) { int mn = arr[i]; int mx = arr[i]; for ( int j = i; j < n; j++) { mx = max(mx, arr[j]); mn = min(mn, arr[j]); sum += (mx - mn); } } return sum; } // Driver Code int main() { vector< int > arr = { 1, 6, 3 }; cout << sumOfDiff(arr); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to find the sum // of the absolute difference // of maximum and minimum of all subarrays static int sumOfDiff( int []arr) { int sum = 0 ; int n = arr.length; for ( int i = 0 ; i < n; i++) { int mn = arr[i]; int mx = arr[i]; for ( int j = i; j < n; j++) { mx = Math.max(mx, arr[j]); mn = Math.min(mn, arr[j]); sum += (mx - mn); } } return sum; } // Driver Code public static void main(String args[]) { int []arr = { 1 , 6 , 3 }; System.out.println(sumOfDiff(arr)); } } // This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach # Function to find the sum # of the absolute difference # of maximum and minimum of all subarrays def sumOfDiff(arr): sum = 0 n = len (arr) for i in range (n): mn = arr[i] mx = arr[i] for j in range (i, n): mx = max (mx, arr[j]) mn = min (mn, arr[j]) sum + = (mx - mn) return sum # Driver Code arr = [ 1 , 6 , 3 ] print (sumOfDiff(arr)) # This code is contributed by Saurabh Jaiswal |
C#
// C# program for the above approach using System; class GFG{ // Function to find the sum of the absolute // difference of maximum and minimum of all // subarrays static int sumOfDiff( int []arr) { int sum = 0; int n = arr.Length; for ( int i = 0; i < n; i++) { int mn = arr[i]; int mx = arr[i]; for ( int j = i; j < n; j++) { mx = Math.Max(mx, arr[j]); mn = Math.Min(mn, arr[j]); sum += (mx - mn); } } return sum; } // Driver Code public static void Main() { int []arr = { 1, 6, 3 }; Console.Write(sumOfDiff(arr)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the sum // of the absolute difference // of maximum and minimum of all subarrays function sumOfDiff(arr) { let sum = 0; let n = arr.length; for (let i = 0; i < n; i++) { let mn = arr[i]; let mx = arr[i]; for (let j = i; j < n; j++) { mx = Math.max(mx, arr[j]); mn = Math.min(mn, arr[j]); sum += (mx - mn); } } return sum; } // Driver Code let arr = [1, 6, 3]; document.write(sumOfDiff(arr)); // This code is contributed by Potta Lokesh </script> |
13
Time complexity: O(N2 )
Auxiliary Space: O(1)
Contact Us