Time Limit Exceeded: How can I optimize my code in Javascript?-CodePudding

I am trying to solve Sum of Subarray Ranges question on leetcode, it's giving me Time Limit Exceeded so I guess my code isn't optimized well and needs more efficient solutions. But I am not so good at it so to be specific how can I remove two for-loops with one in my code.

Ques1: Sum of Subarray Ranges

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray. Return the sum of all subarray ranges of nums. A subarray is a contiguous non-empty sequence of elements within an array.

Example:

Input: nums = [1,2,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0 
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0   0   0   1   1   2 = 4.

Ques link

My code: Test cases: 52/71

var subArrayRanges = function(nums) {
    let maxSub=0;
    for(let i=0; i<nums.length; i  ){
        let arr=[];
        arr.push(nums[i])
        for(let j=i 1; j<nums.length; j  ){
            arr.push(nums[j]);
            maxSub=maxSub (Math.max(...arr)) - (Math.min(...arr));
        }
    }
    return maxSub
};

How can I optimize my code so that it can run all test cases?

CodePudding user response：

A hint for the optimization part: when the j-loop gets a new element, only that element can affect the minimum/maximum of the given subarray. So you don't actually have to build the subarray and run actual min()/max() calls on it, only store its min and max values (which are the same [i] element at the beginning of the inner loop) and compare update them using the incoming new element (the [j] one):

var subArrayRanges = function(nums) {
    let maxSub=0;
    for(let i=0; i<nums.length; i  ){
        let min=nums[i],max=nums[i];
        for(let j=i 1; j<nums.length; j  ){
            if(nums[j]<min)min=nums[j];
            if(nums[j]>max)max=nums[j];
            maxSub=maxSub max-min;
        }
    }
    return maxSub
};