O(n2*k) or worst case O(n3) (As k can reach 10^9) but still TLE


#1

My code follows their algorithm and its time complexity is as mentioned but still getting TLE on some test cases. Anyone know why? (Pretty small code)

int Solution::solve(vector &A, int B)
{
int n = A.size();
vector<vector > dp(n);
B = min(B, n);
for(int i=0;i<n;++i) dp[i] = vector (B+1);

for(int i=0;i<n;++i)
{
    for(int j=0;j<=B;++j)
    {
        if(i==0||j==0) dp[i][j]=0;
        else
        {
            int maxval = max(0, A[i]-A[0]);
            for(int k=1;k<i;++k)
            {
                maxval = max(maxval, dp[k-1][j-1]+A[i]-A[k]);
            }
            maxval = max(maxval, dp[i-1][j]);
            dp[i][j] = maxval;
        }
    }
}
return dp[n-1][B];

}