dimanche 11 juillet 2021

Strange CPP Behaviour

CODE 1

#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>

int LASLengthRecur(vvvi &dp, vi &nums, int idx, int prevIdx, bool isAsc){
    if(idx == nums.size())  return 0;
    if(dp[idx][prevIdx + 1][isAsc? 1: 0] != -1)
        return dp[idx][prevIdx + 1][isAsc? 1: 0];

    int l1 = 0;
    if(isAsc){
        if(prevIdx == -1 || nums[prevIdx] < nums[idx])
            l1 = 1 + LASLengthRecur(dp, nums, idx+1, idx, !isAsc);
    
    }else if(prevIdx == -1 || nums[prevIdx] > nums[idx])
        l1 = 1 + LASLengthRecur(dp, nums, idx+1, idx, !isAsc);

    // Skip the number
    int l2 = LASLengthRecur(dp, nums, idx+1, prevIdx, isAsc);
    
    dp[idx][prevIdx + 1][isAsc? 1: 0] = max(l1, l2);
    return dp[idx][prevIdx + 1][isAsc? 1: 0];
}


int LASLengthI(vi nums){
    
    vvvi dp1(nums.size(), vvi(nums.size(), vi(2, -1)));
    vvvi dp2(nums.size(), vvi(nums.size(), vi(2, -1)));
    return max(LASLengthRecur(dp1, nums, 0, -1, 0),
               LASLengthRecur(dp2, nums, 0, -1, 1));
}

CODE 2

int LASLengthRecur(vvvi &dp, vi &nums, int idx, int prevIdx, bool isAsc){
    if(idx == nums.size())  return 0;
    if(dp[idx][prevIdx + 1][isAsc? 1: 0] != -1)
        return dp[idx][prevIdx + 1][isAsc? 1: 0];

    int l1 = 0;
    if(isAsc && (prevIdx == -1 || nums[prevIdx] < nums[idx]))
         l1 = 1 + LASLengthRecur(dp, nums, idx+1, idx, !isAsc);

    else if(prevIdx == -1 || nums[prevIdx] > nums[idx])
        l1 = 1 + LASLengthRecur(dp, nums, idx+1, idx, !isAsc);

    // Skip the number
    int l2 = LASLengthRecur(dp, nums, idx+1, prevIdx, isAsc);

    dp[idx][prevIdx + 1][isAsc? 1: 0] = max(l1, l2);
    return dp[idx][prevIdx + 1][isAsc? 1: 0];
}

CODE 1 does give correct result but CODE 2 does not give us the correct result. For Input {1, 2, 3, 4} the correct output is 2. CODE 2 gives 4 for the same output. Any specific differences between CODE 1 & CODE 2?

Aucun commentaire:

Enregistrer un commentaire