Auto comment: topic has been updated by iez (previous revision, new revision, compare).

I believe this problem can be directly solved by removing either the minimum or maximum element from both ends of the array.

I think you could use a multi_set to store all the value from the array, and remove either value from both end if is the min or max val from the subarray/subsequence.

Repeat until it's valid. The time complexity is O(nlogn):D

For the above question, I have the following algorithm:

1. Find maximum of the array
2. Find minimum of the array
3. Let index of leftmost element that isnt the maximum or minimum be l
4. Let index rightmost element that isnt the maximum or minimum be r
5. Output l and r if l < r, else output "No such subarray"

Why this works? (For both questions)
1. Case where there isnt such a valid subarray: 
There are only a few cases where there wont exist such a valid subarray: case where the array has exactly 1 or 2 distinct elements and arrays of length 3 with only three distinct elements. It is easy to see why these fail. In these cases either l == r or l > r.
2. Case where there is such a vaild subarray:
By construction, we definitely get a valid subarray. To prove that this is the biggest, assume a bigger subarray B, and call our constructed subarray with l and r as C.
 
Case 2.1: Suppose B is to the left of C
    Then the leftmost element of B is the actual leftmost element which our algorithm will find. So Leftmost element of B is the leftmost element of C. 
Case 2.2: Similarly, suppose B is to the right of C and a similar claim can now be made with the rightmost element of B and C
    So, there is a contradiction in our assumption that B is arger than C i.e it is NOT the case that B is larger than C.
Hence proved, by contradiction that C is the largest such subarray.

Time complexity:
one array pass each for steps 1-2;
Tow array passes each for steps 3-4;
o(1) printing for step 5;
total: o(n);

EDIT: Formatting changes, Corrected steps 3 and 4 and their time complexities

EDIT 2: Added c++ code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll n; cin >> n;
    ll a[n]; for (ll i = 0; i<n; i++) cin >> a[i];
    //Step 1: find max
    ll maxn = LLONG_MIN;
    for (ll i = 0; i<n; i++) {
        if (a[i] > maxn) maxn = a[i];
    }
    //Step 2: find min
    ll minn = LLONG_MAX;
    for (ll i = 0; i<n; i++) {
        if (a[i] < minn) minn = a[i];
    }
    //Step 3: find l
    ll l = -1;
    for (ll i = 0; i<n; i++) {
        if (a[i] != maxn && a[i] != minn) {
            l = i; 
            break;
        }
    }
    //Step 4: find r
    ll r = -1;
    for (ll i = n-1; i>=0; i--) {
        if (a[i] != maxn && a[i] != minn) {
            r = i; 
            break;
        }
    }
    //Step 5: print
    if (l >= r || l == -1 || r == -1) cout << "No such subarray\n";
    else cout << l+1 << " " << r+1 << "\n"; // +1 to correct for 1-indexing
    return 0;
}

Maybe these solutions would work? (First problem: Find a valid subarray (It doesn't have to be the biggest), which means a subbaray of size 1 should be valid, because the last and first element is neither the max or min element of the original array

void solve() {
  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0;i < n;i++) cin >> a[i];
  int minn = *min_element(all(a)), maxx = *max_element(all(a));
  
  for(int i = 0;i < n;i++){
    if(a[i] != minn && a[i] != maxx){cout << a[i]; return;}
  }
  cout << -1;
}

For problem 2 I don't think I'm capable yet.. I have an idea using queues but I'll update soon when I figure it out

If someone has an easier approach, please share. I think we can do d&c. Suppose we split a segment in the middle, and the "optimal" segment lies over this split. Then it consists of a suffix of the left segment, and a prefix of the right segment. We have 2 cases:

• One of the endpoints (left or right) is neither the smallest nor the largest element of the corresponding half.

• The endpoints are the largest (but not smallest) and the smallest (but not largest) in their halfs.

For the first case, we iterate over the other side, and we only need to check the furthest prefix/suffix on the other side that satisfies the first case.

For the second case, we can do 2 pointers approach over the suffixes/prefixes that satisfy this case, and keep track of the furthest suffix/prefix that is still (maybe) possible. For example, if right endpoint is minimum in its half, and left endpoint is maximum, and H is the largest value in the right half, then from the suffix maxima on the left side, we point to the largest one that is strictly less than H. Then we need to check whether the minimum on the left side is less than the right endpoint.

This is O(n log(n)). I feel like there might be a way easier solution, so please tell me if so.

This problem is basically the same as 1793C - Dora and Search

the difficulty of this problem could change depending on whether the array is a permutation or not. A permutation is a more friendly one

First let's keep an array that holds the biggest index such that there exists two indices R[k]: a[i] > a[j] and k <= i < j, or -1 if no index exists, then we can also keep an array that finds the smallest index such that a[i] > a[j] and i < j, or -1 if no index exists, let's call these arrays R and L respectively, then a valid array exists if L[i] < R[i] and L[i] != -1, and the biggest one will be when the R[i] — L[i] is at a maximum, let me demonstrate with your input: 1. idx= 0 1 2 3 4 5 6 2. A = 1 3 2 4 6 5 7 3. L = -1 2 -1 -1 5 -1 -1 4. R = 5 5 5 5 5 -1 -1 from this we can see that the only valid subarray is from [1, 5], since R[1] = 5 > L[1] = 2, and L[1] != -1. Is this approach correct?

Nice problem btw