Longest Increasing Subsequence

                                            
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return *max_element(dp.begin(), dp.end());
    }
};

                                            
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        int maxLength = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
}

                                            
class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        
        dp = [1] * len(nums)
        
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

                                            
int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    
    int dp[numsSize];
    int len = 1;
    dp[0] = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > dp[len - 1]) {
            dp[len] = nums[i];
            len++;
        } else {
            int left = 0, right = len - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (dp[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            dp[right] = nums[i];
        }
    }
    
    return len;
}

                                            
public class Solution {
    public int LengthOfLIS(int[] nums) {
        int n = nums.Length;
        int[] dp = new int[n];
        
        Array.Fill(dp, 1);
        
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return dp.Max();
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    let dp = new Array(nums.length).fill(1);
    let maxLen = 1;
    
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    
    return maxLen;
};

                                            
function lengthOfLIS(nums: number[]): number {
    const dp: number[] = new Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function lengthOfLIS($nums) {
        $n = count($nums);
        $dp = array_fill(0, $n, 1);
        
        for ($i = 1; $i < $n; $i++) {
            for ($j = 0; $j < $i; $j++) {
                if ($nums[$i] > $nums[$j]) {
                    $dp[$i] = max($dp[$i], $dp[$j] + 1);
                }
            }
        }
        
        return max($dp);
    }
}

                                            
class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        
        var dp = [Int](repeating: 1, count: nums.count)
        var maxLength = 1
        
        for i in 0..<nums.count {
            for j in 0..<i {
                if nums[i] > nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
            maxLength = max(maxLength, dp[i])
        }
        
        return maxLength
    }
}

                                            
class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        val dp = IntArray(nums.size) { 1 }
        var maxLen = 1
        for (i in 1 until nums.size) {
            for (j in 0 until i) {
                if (nums[i] > nums[j]) {
                    dp[i] = maxOf(dp[i], dp[j] + 1)
                }
            }
            maxLen = maxOf(maxLen, dp[i])
        }
        return maxLen
    }
}

                                            
class Solution {
  int lengthOfLIS(List<int> nums) {
    if (nums.isEmpty) return 0;
    
    List<int> dp = List.filled(nums.length, 1);
    int maxLength = 1;
    
    for (int i = 1; i < nums.length; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          dp[i] = dp[i].compareTo(dp[j] + 1) > 0 ? dp[i] : dp[j] + 1;
        }
      }
      maxLength = maxLength.compareTo(dp[i]) > 0 ? maxLength : dp[i];
    }
    
    return maxLength;
  }
}

                                            
func lengthOfLIS(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }

    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    maxLength := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        maxLength = max(maxLength, dp[i])
    }

    return maxLength
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def length_of_lis(nums)
    return 0 if nums.empty?
    
    dp = Array.new(nums.length, 1)
    
    (1...nums.length).each do |i|
        (0...i).each do |j|
            if nums[i] > nums[j]
                dp[i] = [dp[i], dp[j] + 1].max
            end
        end
    end
    
    dp.max
end

                                            
object Solution {
    def lengthOfLIS(nums: Array[Int]): Int = {
        val dp = new Array[Int](nums.length)
        var len = 0
        for (num <- nums) {
            var left = 0
            var right = len
            while (left < right) {
                val mid = left + (right - left) / 2
                if (dp(mid) < num) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            dp(left) = num
            if (left == len) {
                len += 1
            }
        }
        len
    }
}

                                            
impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut dp = vec![1; nums.len()];
        
        for i in 0..nums.len() {
            for j in 0..i {
                if nums[i] > nums[j] {
                    dp[i] = dp[i].max(dp[j] + 1);
                }
            }
        }
        
        *dp.iter().max().unwrap_or(&0)
    }
}

To solve this coding challenge, we need to find the longest strictly increasing subsequence in a given integer array. This means that we have to identify the subsequence where each element is larger than the previous one and then return its length. Let's work through a detailed explanation and pseudocode to achieve this.

# Explanation

Understanding the Problem :

Given an integer array
nums

, we need to find the length of the longest subsequence that is strictly increasing.
Example: For the input
nums = [10, 9, 2, 5, 3, 7, 101, 18]

, the longest increasing subsequence is
[2, 3, 7, 101]

with a length of 4.

Dynamic Programming Approach :

We use a dynamic programming approach where we maintain an array
dp

such that
dp[i]

represents the length of the longest increasing subsequence ending at index
i

.
Initially, each element in
dp

is set to 1 because the minimum length of an increasing subsequence that includes only the element itself is 1.

Filling the DP Array :

We iterate through each element and, for each element
nums[i]

, we check all previous elements
nums[j]

where
0 <= j < i

.
If
nums[i] > nums[j]

, it means that
nums[i]

can extend the increasing subsequence ending at
nums[j]

. We update
dp[i]

to be the maximum of its current value and
dp[j] + 1

.

Result :

Once we fill the
dp

array, the length of the longest increasing subsequence would be the maximum value in the
dp

array.

# Detailed Steps in Pseudocode

Here's the step-by-step pseudocode to solve this using dynamic programming:

                                            
# Check if the input array is empty
IF nums is empty THEN
    RETURN 0
END IF

# Initialize the dynamic programming array with ones 
# because the minimum length of an increasing subsequence for any element is 1
dp = array with length of nums filled with 1s

# Start from the second element (index 1) and iterate through the array
FOR i from 1 to length of nums - 1 DO

    # Compare with all previous elements
    FOR j from 0 to i - 1 DO

        # If the current element is greater than the previous element
        IF nums[i] > nums[j] THEN
            # Update the dp[i] with the maximum of its current value and dp[j] + 1
            dp[i] = max(dp[i], dp[j] + 1)
        END IF

    END FOR

END FOR

# The result is the maximum value in the dp array which gives the length of the longest increasing subsequence
RETURN max value in dp

# Explanation with Comments

Now, let's narrate the pseudocode with comments explaining each step:

                                            
# Check if the input array is empty
IF nums is empty THEN
    RETURN 0  # There is no subsequence in an empty array, so return 0
END IF

# Initialize the dynamic programming array with ones because the minimum length 
# of an increasing subsequence for any element is 1
dp = array with length of nums filled with 1s  # dp array to keep track of longest subsequence length

# Start from the second element (index 1) and iterate through the array
FOR i from 1 to length of nums - 1 DO
    # Compare with all previous elements
    FOR j from 0 to i - 1 DO
        # If the current element is greater than the previous element
        IF nums[i] > nums[j] THEN
            # Update the dp[i] with the maximum of its current value and dp[j] + 1
            dp[i] = max(dp[i], dp[j] + 1)  # Extend the subsequence if nums[i] can follow nums[j]
        END IF
    END FOR
END FOR

# The result is the maximum value in the dp array which gives the length of the longest increasing subsequence
RETURN max value in dp  # The maximum value in dp represents the length of the longest increasing subsequence

This detailed explanation and pseudocode methodically break down how to approach and solve the challenge step-by-step, ensuring a thorough understanding of the problem-solving process.