## Given problem

The problem is described in the following link https://codeforces.com/group/FLVn1Sc504/contest/274496/problem/M

It means that we have an array like the below. The output that we need to find is that the index m, n of nums array satisfies nums[i] * (n - m + 1) = max value.

``````Example 1:
Input: nums[] = {3 4 3 1};
Output: 9 1 3

Example 2:
Input: nums[] = {1 2 1 3};
Output: 4 1 4
``````

The requirement of this problem is as same as the problem of https://vnoi.info/wiki/algo/data-structures/deque-min-max.

## Using brute force solution

``````public static void kagain(int[] nums) {
int[] l = new int[nums.length];
int[] r = new int[nums.length];

for (int i = 0; i < nums.length; ++i) {
// Calculate l
l[i] = i;
while (l[i] > -1 && nums[i] <= nums[l[i]]) --l[i];
++l[i];

// Calculate r
r[i] = i;
while (r[i] < nums.length && nums[i] <= nums[r[i]]) ++r[i];
--r[i];
}

int res = nums[0] * (r[0] - l[0] + 1);
for (int i = 1; i < nums.length; ++i) {
int tmp = nums[i] * (r[i] - l[i] + 1);
res = Math.max(res, tmp);
}

System.out.println("Result: " + res);
}
``````

The complexity of this solution:

• Time complexity: O(n^2)
• Space complexity: O(n)

## Using deque solution

``````public static void kagain(int[] nums) {
Deque<Integer> deque = new LinkedList<>();
int[] l = new int[nums.length];
int[] r = new int[nums.length];

// Calculate l
for (int i = 0; i < nums.length; ++i) {
while (deque.size() > 0 && nums[i] <= nums[deque.peekLast()]) deque.pollLast();
l[i] = deque.isEmpty() ? 0 : deque.peekLast() + 1;
}

// Calculate r
deque.clear();
for (int i = nums.length - 1; i >= 0; --i) {
while (deque.size() > 0 && nums[i] <= nums[deque.peekLast()]) deque.pollLast();
r[i] = deque.isEmpty() ? nums.length - 1 : deque.peekLast() - 1;
}

int res = nums[0] * (r[0] - l[0] + 1);
for (int i = 1; i < nums.length; ++i) {
int tmp = nums[i] * (r[i] - l[i] + 1);
res = Math.max(res, tmp);
}

System.out.println("Result: " + res);
}
``````

The complexity of using deque solution:

• Time complexity: O(n)
• Space complexity: O(n)

## Wrapping up

• Understand about how to use deque in this problemâ€™s type.

Refer:

https://nhannguyen95.wordpress.com/2016/01/10/ung-dung-deque-de-tim-min-max-tren-doan-bat-ki-cua-day-so/

https://vnoi.info/wiki/algo/data-structures/deque-min-max

https://mrkolo.wordpress.com/2016/06/04/ky-thuat-deque-tinh-tien/

https://codeforces.com/group/FLVn1Sc504/contest/274496/problem/M