CODEWITHSUNDEEP
c++
Subbu
Subbu

Reputation: 2101

c++ - Multiple conditions in for loop getting incorrect result

Given an array A = [10,9,2,5,3,7,101,18] I am populating another array B of same length such that B[i] is longest increasing sub sequence containing A[i] of subarray A[0,i] (Please refer Longest Increasing Subsequence : https://leetcode.com/problems/longest-increasing-subsequence/ )

For this I am using following loop

for(int i = 1; i < A.size(); i++) { 
    int curr_lis = 1;
    for (int j = 0; j < i; j++)
        if (A[j] < A[i])
            curr_lis = max(curr_lis, B[j] + 1); 
    
    B[i] = curr_lis;
}

This logic correctly populates array B = [1 1 1 2 2 3 4 4 1]

But if I try to merge inner condition with the for-loop condition i.e. (j < i) && (a[j] < a[i]) as shown below

for(int i = 1; i < A.size(); i++) { 
    int curr_lis = 1;
    for(int j = 0; (j < i) && (A[j] < A[i]); j++)
        curr_lis = max(curr_lis, B[j] + 1); 
    
    B[i] = curr_lis;
}

then the array B gets incorrectly populated to B = [1 1 1 1 1 1 2 2 1]

I think I am doing something silly in merging the conditions in for-loop, can someone please help to understand the issue ?

Upvotes: 0

Views: 71

Answers (1)

user5550963
user5550963

Reputation:

Ok, first example will work for each j value and find the maximum value. Second will stop the first time you hit A[j] < A[i]. So what if you have situation like A[i] = 5 and A[j] = 5, but down the road A[j+1] = 6, A[j+2] = 7 ... A[j+100]=1000. Your second loop will say I found maximum its 5, go on and increment i. No A[i] = 6, but j will not go to 6 because of the clause j < i.

Upvotes: 1

Related Questions