Getiing Time Limit Exceeded Error! Is getting subarrays possible in less than O(n^3)?


#1

vector findSubArray(vector &A){

vector <long long int> G;
int max = INT_MIN;

for(int i = 0; i < A.size(); i++){
    for(int j = i; j < A.size(); j++){
        for(int k = i; k <= j; k++ ){
            if(A[k] > max)
             max = A[k];
        }
        G.push_back(max);
        max = INT_MIN;
    }
}

return G;
}

vector findProductDivisors(vector &G){

const int M = 1e9+7;

for(long long int i = 0; i < G.size(); i++)
{    long long int mulDivisors = 1;
        long long int a = G[i];

    for(long long int i = 1; i <= sqrt(a); i++){    
    
    if(a%i == 0)
        if(a/i == i)
        mulDivisors =  (mulDivisors * i) % M; // when i is square root of a
        else{
        mulDivisors =  (mulDivisors * i) % M;
        mulDivisors =  (mulDivisors * (a/i)) %M;
        }
    }
G[i] = mulDivisors;
}

return G;

}

vector Solution::solve(vector &A, vector &B) {

vector <long long int> G;

G = findSubArray(A);

G = findProductDivisors(G); 

 sort(G.begin(), G.end(), greater <int>());

vector<int> H;
for(int i=0;i<B.size();i++) {
    H.push_back(G[B[i]-1]);
}
return H;

}


#2

try this

    for( long long i = 0; i < A.size(); i++){
        
        long long left = 1, right = 1;
        long j = i + 1; 
        while( j < A.size() && A[j] <= A[i]){
            right++;
            j++;
        }
        j = i - 1;
        while( j >= 0 && A[j] < A[i]){
            left++;
            j--;
        }
        
        count[ A[i] ] += left * right;
    }