Open In App

Sum of maximum of all subarrays | Divide and Conquer

Last Updated : 09 Nov, 2021
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Given an array arr[] of length N, the task is to find the sum of the maximum elements of every possible sub-array of the array.
Examples: 
 

Input : arr[] = {1, 3, 1, 7}
Output : 42
Max of all sub-arrays:
{1} - 1
{1, 3} - 3
{1, 3, 1} - 3
{1, 3, 1, 7} - 7
{3} - 3
{3, 1} - 3
{3, 1, 7} - 7 
{1} - 1
{1, 7} - 7
{7} - 7
1 + 3 + 3 + 7 + 3 + 3 + 7 + 1 + 7 + 7 = 42

Input : arr[] = {1, 1, 1, 1, 1}
Output : 15

 

We have already discussed an O(N) approach using stack for this problem in this article.
Approach : 
In this article, we will learn how to solve this problem using divide and conquer
Let’s assume that element at ith index is largest of all. For any sub-array that contains index ‘i’, the element at ‘i’ will always be maximum in the sub-array. 
If element at ith index is largest, we can safely say, that element ith index will be largest in (i+1)*(N-i) subarrays. So, its total contribution will be arr[i]*(i+1)*(N-i). Now, we will divide the array in two parts, (0, i-1) and (i+1, N-1) and apply the same algorithms to both of them separately.
So our general recurrence relation will be: 
 

maxSumSubarray(arr, l, r) = arr[i]*(r-i+1)*(i-l+1) 
                            + maxSumSubarray(arr, l, i-1)
                            + maxSumSubarray(arr, i+1, r)
where i is index of maximum element in range [l, r].

Now, we need a way to efficiently answer rangeMax() queries. Segment tree will be an efficient way to answer this query. We will need to answer this query at most N times. Thus, the time complexity of our divide and conquer algorithm will O(Nlog(N)). 
If we have to answer the problem “Sum of minimum of all subarrays” then we will use the segment tree to answer rangeMin() queries. For this, you can go through the article segment tree range minimum.
Below is the implementation code: 
 

C++




// C++ implementation of the above approach
 
#include <bits/stdc++.h>
#define seg_max 51
using namespace std;
 
// Array to store segment tree.
// In first we will store the maximum
// of a range
// In second, we will store index of
// that range
pair<int, int> seg_tree[seg_max];
 
// Size of array declared global
// to maintain simplicity in code
int n;
 
// Function to build segment tree
pair<int, int> buildMaxTree(int l, int r, int i, int arr[])
{
    // Base case
    if (l == r) {
        seg_tree[i] = { arr[l], l };
        return seg_tree[i];
    }
 
    // Finding the maximum among left and right child
    seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr),
                      buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr));
 
    // Returning the maximum to parent
    return seg_tree[i];
}
 
// Function to perform range-max query in segment tree
pair<int, int> rangeMax(int l, int r, int arr[],
                        int i = 0, int sl = 0, int sr = n - 1)
{
    // Base cases
    if (sr < l || sl > r)
        return { INT_MIN, -1 };
    if (sl >= l and sr <= r)
        return seg_tree[i];
 
    // Finding the maximum among left and right child
    return max(rangeMax(l, r, arr, 2 * i + 1, sl, (sl + sr) / 2),
               rangeMax(l, r, arr, 2 * i + 2, (sl + sr) / 2 + 1, sr));
}
 
// Function to find maximum sum subarray
int maxSumSubarray(int arr[], int l = 0, int r = n - 1)
{
    // base case
    if (l > r)
        return 0;
 
    // range-max query to determine
    // largest in the range.
    pair<int, int> a = rangeMax(l, r, arr);
 
    // divide the array in two parts
    return a.first * (r - a.second + 1) * (a.second - l + 1)
           + maxSumSubarray(arr, l, a.second - 1)
           + maxSumSubarray(arr, a.second + 1, r);
}
 
// Driver Code
int main()
{
    // Input array
    int arr[] = { 1, 3, 1, 7 };
 
    // Size of array
    n = sizeof(arr) / sizeof(int);
 
    // Builind the segment-tree
    buildMaxTree(0, n - 1, 0, arr);
 
    cout << maxSumSubarray(arr);
 
    return 0;
}


Java




// Java implementation of the above approach
class GFG {
    static class pair {
        int first, second;
 
        public pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
 
    static final int seg_max = 51;
     
    // Array to store segment tree.
    // In first we will store the maximum
    // of a range
    // In second, we will store index of
    // that range
    static pair[] seg_tree = new pair[seg_max];
 
    // Size of array declared global
    // to maintain simplicity in code
    static int n;
 
    // Function to build segment tree
    static pair buildMaxTree(int l, int r, int i, int arr[])
    {
        // Base case
        if (l == r) {
            seg_tree[i] = new pair(arr[l], l);
            return seg_tree[i];
        }
 
        // Finding the maximum among left and right child
        seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr),
                buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr));
 
        // Returning the maximum to parent
        return seg_tree[i];
    }
 
    // Function to perform range-max query in segment tree
    static pair rangeMax(int l, int r, int arr[],
                        int i, int sl, int sr)
    {
        // Base cases
        if (sr < l || sl > r)
            return new pair(Integer.MIN_VALUE, -1);
        if (sl >= l && sr <= r)
            return seg_tree[i];
 
        // Finding the maximum among left and right child
        return max(rangeMax(l, r, arr, 2 * i + 1, sl, (sl + sr) / 2),
                rangeMax(l, r, arr, 2 * i + 2, (sl + sr) / 2 + 1, sr));
    }
 
    static pair max(pair f, pair s) {
        if (f.first > s.first)
            return f;
        else
            return s;
    }
 
    // Function to find maximum sum subarray
    static int maxSumSubarray(int arr[], int l, int r)
    {
        // base case
        if (l > r)
            return 0;
 
        // range-max query to determine
        // largest in the range.
        pair a = rangeMax(l, r, arr, 0, 0, n - 1);
 
        // divide the array in two parts
        return a.first * (r - a.second + 1) * (a.second - l + 1)
                + maxSumSubarray(arr, l, a.second - 1)
                + maxSumSubarray(arr, a.second + 1, r);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Input array
        int arr[] = { 1, 3, 1, 7 };
 
        // Size of array
        n = arr.length;
 
        // Builind the segment-tree
        buildMaxTree(0, n - 1, 0, arr);
 
        System.out.print(maxSumSubarray(arr, 0, n - 1));
    }
}
 
// This code is contributed by 29AjayKumar


Python3




# Python3 implementation of the above approach
import sys
 
seg_max = 51
       
# Array to store segment tree.
# In first we will store the maximum
# of a range
# In second, we will store index of
# that range
seg_tree = [[] for i in range(seg_max)]
 
# Function to build segment tree
def buildMaxTree(l, r, i, arr):
    global n, seg_tree, seg_max
    # Base case
    if l == r:
        seg_tree[i] = [arr[l], l]
        return seg_tree[i]
 
    # Finding the maximum among left and right child
    seg_tree[i] = max(buildMaxTree(l, int((l + r) / 2), 2 * i + 1, arr), buildMaxTree(int((l + r) / 2) + 1, r, 2 * i + 2, arr))
 
    # Returning the maximum to parent
    return seg_tree[i]
 
# Function to perform range-max query in segment tree
def rangeMax(l, r, arr, i, sl, sr):
    global n, seg_tree, seg_max
     
    # Base cases
    if sr < l or sl > r:
        return [-sys.maxsize, -1]
    if sl >= l and sr <= r:
        return seg_tree[i]
 
    # Finding the maximum among left and right child
    return max(rangeMax(l, r, arr, 2 * i + 1, sl, int((sl + sr) / 2)), rangeMax(l, r, arr, 2 * i + 2, int((sl + sr) / 2) + 1, sr))
 
def Max(f, s):
    if f[0] > s[0]:
        return f
    else:
        return s
 
# Function to find maximum sum subarray
def maxSumSubarray(arr, l, r):
    # base case
    if l > r:
        return 0
 
    # range-max query to determine
    # largest in the range.
    a = rangeMax(l, r, arr, 0, 0, n - 1)
 
    # divide the array in two parts
    return a[0] * (r - a[1] + 1) * (a[1] - l + 1) + maxSumSubarray(arr, l, a[1] - 1) + maxSumSubarray(arr, a[1] + 1, r)
 
# Input array
arr = [ 1, 3, 1, 7 ]
 
# Size of array
n = len(arr)
 
# Builind the segment-tree
buildMaxTree(0, n - 1, 0, arr)
 
print(maxSumSubarray(arr, 0, n - 1))
 
# This code is contributed by decode2207.


C#




// C# implementation of the above approach
using System;
 
class GFG {
    class pair {
        public int first, second;
  
        public pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
  
    static readonly int seg_max = 51;
      
    // Array to store segment tree.
    // In first we will store the maximum
    // of a range
    // In second, we will store index of
    // that range
    static pair[] seg_tree = new pair[seg_max];
  
    // Size of array declared global
    // to maintain simplicity in code
    static int n;
  
    // Function to build segment tree
    static pair buildMaxTree(int l, int r, int i, int []arr)
    {
        // Base case
        if (l == r) {
            seg_tree[i] = new pair(arr[l], l);
            return seg_tree[i];
        }
  
        // Finding the maximum among left and right child
        seg_tree[i] = max(buildMaxTree(l, (l + r) / 2, 2 * i + 1, arr),
                buildMaxTree((l + r) / 2 + 1, r, 2 * i + 2, arr));
  
        // Returning the maximum to parent
        return seg_tree[i];
    }
  
    // Function to perform range-max query in segment tree
    static pair rangeMax(int l, int r, int []arr,
                        int i, int sl, int sr)
    {
        // Base cases
        if (sr < l || sl > r)
            return new pair(int.MinValue, -1);
        if (sl >= l && sr <= r)
            return seg_tree[i];
  
        // Finding the maximum among left and right child
        return max(rangeMax(l, r, arr, 2 * i + 1, sl, (sl + sr) / 2),
                rangeMax(l, r, arr, 2 * i + 2, (sl + sr) / 2 + 1, sr));
    }
  
    static pair max(pair f, pair s) {
        if (f.first > s.first)
            return f;
        else
            return s;
    }
  
    // Function to find maximum sum subarray
    static int maxSumSubarray(int []arr, int l, int r)
    {
        // base case
        if (l > r)
            return 0;
  
        // range-max query to determine
        // largest in the range.
        pair a = rangeMax(l, r, arr, 0, 0, n - 1);
  
        // divide the array in two parts
        return a.first * (r - a.second + 1) * (a.second - l + 1)
                + maxSumSubarray(arr, l, a.second - 1)
                + maxSumSubarray(arr, a.second + 1, r);
    }
  
    // Driver Code
    public static void Main(String[] args)
    {
        // Input array
        int []arr = { 1, 3, 1, 7 };
  
        // Size of array
        n = arr.Length;
  
        // Builind the segment-tree
        buildMaxTree(0, n - 1, 0, arr);
  
        Console.Write(maxSumSubarray(arr, 0, n - 1));
    }
}
 
// This code is contributed by PrinciRaj1992


Javascript




<script>
 
// JavaScript implementation of the above approach
 
class pair
{
    constructor(first,second)
    {
        this.first = first;
            this.second = second;
    }
}
 
let seg_max = 51;
 
// Array to store segment tree.
    // In first we will store the maximum
    // of a range
    // In second, we will store index of
    // that range
let seg_tree = new Array(seg_max);
 
// Size of array declared global
    // to maintain simplicity in code
let n;
 
// Function to build segment tree
function buildMaxTree(l,r,i,arr)
{
     // Base case
        if (l == r) {
            seg_tree[i] = new pair(arr[l], l);
            return seg_tree[i];
        }
   
        // Finding the maximum among left and right child
        seg_tree[i] = max(buildMaxTree(l, Math.floor((l + r) / 2),
        2 * i + 1, arr), buildMaxTree(Math.floor((l + r) / 2) +
        1, r, 2 * i + 2, arr));
   
        // Returning the maximum to parent
        return seg_tree[i];
}
 
// Function to perform range-max query in segment tree
function rangeMax(l,r,arr,i,sl,sr)
{
    // Base cases
        if (sr < l || sl > r)
            return new pair(Number.MIN_VALUE, -1);
        if (sl >= l && sr <= r)
            return seg_tree[i];
   
        // Finding the maximum among left and right child
        return max(rangeMax(l, r, arr, 2 * i + 1, sl,
                   Math.floor((sl + sr) / 2)),
                rangeMax(l, r, arr, 2 * i + 2,
                Math.floor((sl + sr) / 2) + 1, sr));
}
 
function max(f,s)
{
    if (f.first > s.first)
            return f;
        else
            return s;
}
 
// Function to find maximum sum subarray
function maxSumSubarray(arr,l,r)
{
    // base case
        if (l > r)
            return 0;
   
        // range-max query to determine
        // largest in the range.
        let a = rangeMax(l, r, arr, 0, 0, n - 1);
   
        // divide the array in two parts
        return a.first * (r - a.second + 1) * (a.second - l + 1)
                + maxSumSubarray(arr, l, a.second - 1)
                + maxSumSubarray(arr, a.second + 1, r);
}
 
// Driver Code
// Input array
let arr = [ 1, 3, 1, 7 ];
 
// Size of array
n = arr.length;
 
// Builind the segment-tree
buildMaxTree(0, n - 1, 0, arr);
 
document.write(maxSumSubarray(arr, 0, n - 1));
 
// This code is contributed by rag2127
 
</script>


Output: 

42

 

Time complexity : O(Nlog(N))
 



Similar Reads

Maximum Subarray Sum using Divide and Conquer algorithm
You are given a one dimensional array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum. For example, if the given array is {-2, -5, 6, -2, -3, 1, 5, -6}, then the maximum subarray sum is 7 (see highlighted elements). Recommended: Please solve it on “PRACTICE ” first, befo
12 min read
Difference between Greedy Algorithm and Divide and Conquer Algorithm
Greedy algorithm and divide and conquer algorithm are two common algorithmic paradigms used to solve problems. The main difference between them lies in their approach to solving problems. Greedy Algorithm:The greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage wit
3 min read
Comparison among Greedy, Divide and Conquer and Dynamic Programming algorithm
Greedy algorithm, divide and conquer algorithm, and dynamic programming algorithm are three common algorithmic paradigms used to solve problems. Here's a comparison among these algorithms: Approach:Greedy algorithm: Makes locally optimal choices at each step with the hope of finding a global optimum.Divide and conquer algorithm: Breaks down a probl
4 min read
Search in a Row-wise and Column-wise Sorted 2D Array using Divide and Conquer algorithm
Given an n x n matrix, where every row and column is sorted in increasing order. Given a key, how to decide whether this key is in the matrix. A linear time complexity is discussed in the previous post. This problem can also be a very good example for divide and conquer algorithms. Following is divide and conquer algorithm.1) Find the middle elemen
15+ min read
Advantages and Disadvantages of Divide and Conquer Algorithms
Divide and Conquer is an algorithmic paradigm in which the problem is solved using the Divide, Conquer, and Combine strategy. A typical divide-and-conquer algorithm solves a problem using the following three steps: Divide: This involves dividing the problem into smaller sub-problems.Conquer: Solve sub-problems by calling recursively until solved.Co
2 min read
Closest Pair of Points using Divide and Conquer algorithm
We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for dist
15+ min read
Advanced master theorem for divide and conquer recurrences
The Master Theorem is a tool used to solve recurrence relations that arise in the analysis of divide-and-conquer algorithms. The Master Theorem provides a systematic way of solving recurrence relations of the form: T(n) = aT(n/b) + f(n) where a, b, and f(n) are positive functions and n is the size of the problem. The Master Theorem provides conditi
5 min read
Dynamic Programming vs Divide-and-Conquer
In this article I’m trying to explain the difference/similarities between dynamic programming and divide and conquer approaches based on two examples: binary search and minimum edit distance (Levenshtein distance).The ProblemWhen I started to learn algorithms it was hard for me to understand the main idea of dynamic programming (DP) and how it is d
12 min read
Merge K sorted arrays | Set 3 ( Using Divide and Conquer Approach )
Giving k sorted arrays, each of size N, the task is to merge them into a single sorted array. Examples: Input: arr[][] = {{5, 7, 15, 18}, {1, 8, 9, 17}, {1, 4, 7, 7}} Output: {1, 1, 4, 5, 7, 7, 7, 8, 9, 15, 17, 18} Input: arr[][] = {{3, 2, 1} {6, 5, 4}} Output: {1, 2, 3, 4, 5, 6} Prerequisite: Merge SortSimple Approach: A simple solution is to appe
15+ min read
Merge K sorted arrays of different sizes | ( Divide and Conquer Approach )
Given k sorted arrays of different length, merge them into a single array such that the merged array is also sorted.Examples: Input : {{3, 13}, {8, 10, 11} {9, 15}} Output : {3, 8, 9, 10, 11, 13, 15} Input : {{1, 5}, {2, 3, 4}} Output : {1, 2, 3, 4, 5} Let S be the total number of elements in all the arrays.Simple Approach: A simple approach is to
8 min read
Divide and Conquer Optimization in Dynamic Programming
Dynamic programming (DP) is arguably the most important tool in a competitive programmer's repertoire. There are several optimizations in DP that reduce the time complexity of standard DP procedures by a linear factor or more, such as Knuth's optimization, Divide and Conquer optimization, the Convex Hull Trick, etc. They are, of paramount importanc
15+ min read
Divide and Conquer definition & meaning in DSA
Divide and Conquer is a type of algorithm which involves breaking down a difficult problem into smaller subproblems, solving the subproblems individually and then merging the solutions of those subproblems to solve the actual problem. Properties of Divide and Conquer:Divides the problem into smaller subproblems.Each subproblem is solved independent
2 min read
Divide and Conquer | Set 5 (Strassen's Matrix Multiplication)
Given two square matrices A and B of size n x n each, find their multiplication matrix. Naive Method: Following is a simple way to multiply two matrices. C/C++ Code void multiply(int A[][N], int B[][N], int C[][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i][j] = 0; for (int k = 0; k < N; k++) { C[i][j] += A[i][k]*B[
15+ min read
Tiling Problem using Divide and Conquer algorithm
Given a n by n board where n is of form 2k where k >= 1 (Basically n is a power of 2 with minimum value as 2). The board has one missing cell (of size 1 x 1). Fill the board using L shaped tiles. A L shaped tile is a 2 x 2 square with one cell of size 1x1 missing. Figure 1: An example inputThis problem can be solved using Divide and Conquer. Bel
15+ min read
Longest Common Prefix using Divide and Conquer Algorithm
Given a set of strings, find the longest common prefix. Examples: Input : {“geeksforgeeks”, “geeks”, “geek”, “geezer”} Output : "gee" Input : {"apple", "ape", "april"} Output : "ap" We have discussed word by word matching and character by character matching algorithms.In this algorithm, a divide and conquer approach is discussed. We first divide th
7 min read
Convex Hull using Divide and Conquer Algorithm
In computational geometry, a convex hull is the smallest convex polygon that contains a given set of points. It is a fundamental concept with applications in various fields such as computer graphics, robotics, and image processing. Importance of Convex Hull:Convex hulls are important in computational geometry for several reasons: Collision detectio
15 min read
Divide and Conquer in Python
Divide and Conquer is an effective approach for managing challenges that divides a major problem into smaller, easier-to-manage subproblems. The solution to the main problem is obtained by combining the final solutions from multiple individually solved subproblems. This approach works especially well with issues that naturally break down into diffe
3 min read
Karatsuba algorithm for fast multiplication using Divide and Conquer algorithm
Given two binary strings that represent value of two integers, find the product of two strings. For example, if the first bit string is "1100" and second bit string is "1010", output should be 120. For simplicity, let the length of two strings be same and be n. A Naive Approach is to follow the process we study in school. One by one take all bits o
15+ min read
Divide and Conquer Algorithm
Divide and Conquer algorithm is a problem-solving strategy that involves breaking down a complex problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem. It is a widely used algorithmic technique in computer science and mathematics. Example: In the Merge Sort algori
4 min read
Split array into K subarrays such that sum of maximum of all subarrays is maximized
Given an array arr[] of size N and a number K, the task is to partition the given array into K contiguous subarrays such that the sum of the maximum of each subarray is the maximum possible. If it is possible to split the array in such a manner, then print the maximum possible sum. Otherwise, print "-1". Examples: Input: arr[] = {5, 3, 2, 7, 6, 4},
11 min read
Split into K subarrays to minimize the maximum sum of all subarrays
Given an Array[] of N elements and a number K. ( 1 <= K <= N ) . Split the given array into K subarrays (they must cover all the elements). The maximum subarray sum achievable out of K subarrays formed, must be the minimum possible. Find that possible subarray sum.Examples: Input : Array[] = {1, 2, 3, 4}, K = 3 Output : 4 Optimal Split is {1,
15 min read
Split given arrays into subarrays to maximize the sum of maximum and minimum in each subarrays
Given an array arr[] consisting of N integers, the task is to maximize the sum of the difference of the maximum and minimum in each subarrays by splitting the given array into non-overlapping subarrays. Examples: Input: arr[] = {8, 1, 7, 9, 2}Output: 14Explanation:Split the given array arr[] as {8, 1}, {7, 9, 2}. Now, the sum of the difference maxi
7 min read
Maximum XOR value of maximum and second maximum element among all possible subarrays
Given an array arr[] of N distinct positive integers, let's denote max(i, j) and secondMax(i, j) as the maximum and the second maximum element of the subarray arr[i...j]. The task is to find the maximum value of max(i, j) XOR secondMax(i, j) for all possible values of i and j. Note that the size of the subarray must be at least two.Examples: Input:
5 min read
Sum of maximum of all subarrays by adding even frequent maximum twice
Given an array arr[] consisting of N integers (All array elements are a perfect power of 2), the task is to calculate the sum of the maximum elements in all the subarrays. Note: If the frequency of the maximum element in a subarray is even, add twice the value of that element to the sum. Examples: Input: arr[] = {1, 2}Output: 5Explanation: All poss
15+ min read
Divide array in two Subsets such that sum of square of sum of both subsets is maximum
Given an integer array arr[], the task is to divide this array into two non-empty subsets such that the sum of the square of the sum of both the subsets is maximum and sizes of both the subsets must not differ by more than 1.Examples: Input: arr[] = {1, 2, 3} Output: 26 Explanation: Sum of Subset Pairs are as follows (1)2 + (2 + 3)2 = 26 (2)2 + (1
6 min read
Sliding Window Maximum (Maximum of all subarrays of size k) using stack in O(n) time
Given an array arr[] of N integers and another integer k ? N. The task is to find the maximum element of every sub-array of size k. Examples: Input: arr[] = {9, 7, 2, 4, 6, 8, 2, 1, 5} k = 3 Output: 9 7 6 8 8 8 5 Explanation: Window 1: {9, 7, 2}, max = 9 Window 2: {7, 2, 4}, max = 7 Window 3: {2, 4, 6}, max = 6 Window 4: {4, 6, 8}, max = 8 Window 5
8 min read
Sliding Window Maximum (Maximum of all subarrays of size K)
Given an array and an integer K, find the maximum for each and every contiguous subarray of size K. Examples : Input: arr[] = {1, 2, 3, 1, 4, 5}, K = 3 Output: 3 3 4 5Explanation: Maximum of 1, 2, 3 is 3 Maximum of 2, 3, 1 is 3 Maximum of 3, 1, 4 is 4 Maximum of 1, 4, 5 is 5 Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4 Output: 10 10 10
15+ min read
Minimize range [L, R] to divide Array into K subarrays with majority elements in [L, R]
Given an array arr[] of size N, the task is to find the minimum value range [L, R] such that: The array can be divided into K sub-arrays.The elements within the range [L, R] are greater than the elements which are out of the range[l, r]. Examples: Input: arr[] = {1, 2, 2, 2}, K = 2Output: 2 2Explanation: [2, 2] is the range with minimum distance wh
12 min read
Divide an array into k subarrays with minimum cost II
Given an array of integers arr[] of length n and two positive integers kk and len. The cost of an array is the value of its first element. For example, the cost of [2,3,4] is 2 and the cost of [4,1,2] is 4. You have to divide arr[] into k disjoint contiguous subarrays such that the difference between the starting index of the second subarray and th
11 min read
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: 7Explanation: 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 -
5 min read
three90RightbarBannerImg