+1 vote
261 views
\begin{align*} & a[n] = \{x_1,x_2,x_3,x_4,....,x_n\} \text{ is an array of integers where } n,x_i > 0. \\ & A = \left [ \text{min}\left ( x_i,x_j \right ) \right ] \cdot \left ( j-i \right ) \text{ where } j > i \text{ and } i,j \leq n \\ & \text{What is the best time complexity to find out the value of } A_{\bf max} \; ? \end{align*}
| 261 views
0
In order to find : A = [ min (x i,x j) ] ⋅ ( j− i ) where j>i and i,j≤n

for every index of a[o], we have to check for all the elements of indexes a[1] to a[n.]

for next index of a[1], I have to check for all the elements of indexes a[2] to a[n]

similarly it will take O(N^2) time to do this. then after doing this.

O(N) time for finding maximum values in all the values of A.

so,  i think O(n^2) will be complexity...
0
Any better way?
0
best case should be for array A[]={1,2,3,4,5}

and worst case ={5,4,3,2,1}

Now, for best case will be some miiddle elements of array
0
O(n) is available.
0
@srestha,how r u defining it as worst or best case?
0
no no , that shouldnot be. It could be any arbitrary array

like   49, 37,32 , 33,38 , 50

In that case  1st element will be answer. rt?
+1
yes,here answer will be 49*5 cuz max numbers are at the corners
+1
Using divide and conquer, it can be computed in O(nlogn) time..
0

joshi_nitish ..you can write an implementation and comment here or answer. That would be useful.

// array : a[n]
int left = 1;
int right = n;
int max = -1;
int m = 0;
while(left <= right) {
m = min(a[left],a[right])*( right - left );
if(max < m) max = m;
if(a[left] < a[right]) {
left++;
} else if(a[left] > a[right]) {
right--;
} else {
left++;
right--;
}
}
return max;
by Veteran (57.2k points)
selected by
0

doesnt look correct to me. try this case:

3
5 1 2

+1

@air1

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& a) {
int left = 0; // I modified it to 1 in the answer
int right = a.size() - 1; // I modified it to n in the answer
long maxx = -1;
int m = 0;
while(left <= right) {
m = min(a[left],a[right])*(right-left);
if(maxx < m) maxx = m;
if(a[left] < a[right]) {
left++;
} else if(a[left] > a[right]) {
right--;
} else {
left++;
right--;
}
}
return maxx;
}
int main() {
std::vector<int> v;
v.push_back(5);
v.push_back(1);
v.push_back(2);
cout << solve(v) << endl;
}

//

Output $4$

+1
didnt notice that earlier. its correct.