in Algorithm Challenges
1,048 views
1 vote
1 vote
$\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
1.0k views

4 Comments

yes,here answer will be 49*5 cuz max numbers are at the corners
1
1
Using divide and conquer, it can be computed in O(nlogn) time..
1
1

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

0
0

1 Answer

3 votes
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;
selected by
by

3 Comments

doesnt look correct to me. try this case:

3
5 1 2

your code gives 2, answer is 4.

0
0

@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
1
didnt notice that earlier. its correct.
1
1