0 like 0 dislike
447 views
Expected Time Complexity : O(N) , where 'N'  is the size of the array .

1<=A[i]<=1000000

1<=N<=100000

Example :

100 200 400

Output : 3 ( (100),(200),(100,200) are the subarrays which don't contain the maximum element in them)

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code
in Algorithms and Problems by Expert (19,320 points) | 447 views

1 Answer

1 like 0 dislike
Best answer
With every increase in length of array, number of subarray increases by n

example arr = {3,2,5} total Possible subarray is 1 + 2 + 3 = 6;

example arr = {1,2,3,2} total Possible subarray is 1 + 2 + 3 + 4 = 10;

so in this question find the count of all consecutive elements that doesnot containg maxNumber, and return the total number of subarrays.

Probably this is it, let me know if logic is wrong


#include<bits/stdc++.h>

using namespace std;

int32_t main()

{

    vector<int> TC1 = {1,2,3,9};   // output  = 6    {1,2,3, 12 , 23, 123}

    vector<int> TC2 = {1,9,3,9};   // output = 2     {1,3}

    vector<int> TC3 = {1,9,3,8};   // output = 4     {1,3,8,38}

    vector<int> TC4 = {9};         // output = 0     {}


    // CODE BEGINS

    vector<int> a = TC1;

    int maxElement = *max_element(a.begin() , a.end());


    int ans = 0,

        ct = 0;

    for(auto i : a)

        {

            if(i != maxElement)

                    ++ct,

                    ans += ct;

            else

                ct = 0;

        }

    cout<<"ans is "<<ans;

}
by Expert (1,790 points)
selected by
0 0
Brilliant , the original version of this problem asked to find the number of sub-arrays which do contain the largest element :-)
I hope solution for this helps in that one too :-)