M.KAGAIN

Given problem
Using brute force solution
Using deque solution
Wrapping up

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;
        deque.addLast(i);
    }

    // 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;
        deque.addLast(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);
}