1793. Maximum Score of a Good Subarray

You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], …, nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

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

class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int res = nums[k], l = k, r = k, n = nums.size(), mi = nums[k];
        while(nums.size() != 1) {
            if(l != 0 and nums[l-1] >= mi) l--;
            else if(r != n - 1 and nums[r + 1] >= mi) r++;
            else if(l != 0 and r != n - 1) {
                if(nums[l-1] >= nums[r+1]) l--;
                else r++;
            } else if(l == 0) r++;
            else l--;
            
            mi = min({mi, nums[l], nums[r]});
            res = max(res, mi * (r - l + 1));
            
            if(l == 0 and r == n - 1) break;
        }
        return res;
    }
};