The Gateway to Computer Science Excellence
+1 vote
255 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*}$
in Algorithm Challenges by Veteran (57k points) | 255 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.

1 Answer

+3 votes
Best answer
// 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 (57k points)
selected by
0

doesnt look correct to me. try this case:

3
5 1 2

your code gives 2, answer is 4.

+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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,479 answers
195,421 comments
100,553 users