2552. Count Increasing Quadruplets

link

TLE

Time complexity (N^2) 4000 ^ 2 ~= 10^7

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:

        n = len(nums)
        nums = [0] + nums

        pre = [[0] * (n+2) for i in range(n+2)]
        post = [[0] * (n+2) for i in range(n+2)]

        for i in range(1, n+1):
            for j in range(1, n+1):
                if nums[i] < j:
                    pre[i][j] = pre[i-1][j] + 1
                else:
                    pre[i][j] = pre[i-1][j]

        for i in range(n, 0, -1):
            for j in range(1, n + 1):
                if nums[i] > j:
                    post[i][j] = post[i+1][j] + 1
                else:
                    post[i][j] = post[i+1][j]



        res = 0
        for i in range(1, n+1):
            for j in range(1, i):
                if nums[j] > nums[i]:
                    
                    res += pre[j-1][nums[i]] * post[i+1][nums[j]]
     


        return res

class Solution:
    def countQuadruplets(self, A: List[int]) -> int:
        n = len(A)
        dp = [0]*n  # Number of growing i->k->j ending at j.
        res = 0
        for j, v in enumerate(A):
            cnt = 0   # cnt_j counts A[i] < A[j] seen so far
            for i in range(j):
                if A[i] > v:
                    dp[i] += cnt  # (we found cnt of {i},j,k = (optimised),i,k)
                else:
                    res += dp[i]  # our i,j = desc j,l ; 
                    cnt += 1      # our i,j = desc i,k
        return res