0 like 0 dislike
1,291 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 .

3)Use Format option while adding code
| 1,291 views

1 like 0 dislike
```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
selected
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 :-)