حل مشكلة أطول تسلسل تصاعدي (Longest Increasing Subsequence) باستخدام البرمجة الديناميكية مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

وصف المشكلة:
مشكلة أطول تسلسل تصاعدي (Longest Increasing Subsequence – LIS) هي إيجاد أطول تسلسل متزايد من الأعداد ضمن مصفوفة معينة بحيث يكون كل عنصر في التسلسل أكبر من العنصر الذي يسبقه.

حالة استخدام:
يُستخدم هذا النوع من المشكلات في مجالات متعددة مثل تحليل السلاسل الزمنية، وتحليل ترتيب البيانات، وإيجاد التسلسل الأطول في بيئات مختلفة مثل أنظمة البورصة وغيرها.

المدخلات والمخرجات:

• المدخلات: مصفوفة من الأعداد الصحيحة.
• المخرجات: طول أطول تسلسل تصاعدي.

2. شرح تعليمي للحل

لحل مشكلة أطول تسلسل تصاعدي، يمكننا استخدام البرمجة الديناميكية. الفكرة الأساسية هي إنشاء مصفوفة للمساعدة تُستخدم لتخزين طول أطول تسلسل تصاعدي ينتهي بكل عنصر في المصفوفة الأصلية.

• نبدأ بمصفوفة مساعدة بنفس حجم المصفوفة الأصلية، ونملأها بقيمة 1 لأن كل عنصر يمثل تسلسلاً تصاعديًا بطوله 1 على الأقل.
• نمر عبر المصفوفة ونحدد أطول تسلسل يمكن الحصول عليه عند كل عنصر، باستخدام نتائج العناصر السابقة.
• نأخذ القيمة القصوى من مصفوفة المساعدة في النهاية كطول أطول تسلسل تصاعدي.

تعقيد الوقت:

• O(n²)، حيث n هو عدد العناصر في المصفوفة.

تعقيد المساحة:

• O(n) لاستخدام المصفوفة المساعدة.

3. الحل في Python

def length_of_lis(nums):
    if not nums:
        return 0

    lis = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(0, i):
            if nums[i] > nums[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    return max(lis)

# استخدام المثال
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print("طول أطول تسلسل تصاعدي هو:", length_of_lis(nums))

4. الحل في Java

public class LongestIncreasingSubsequence {

    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        
        int[] lis = new int[nums.length];
        int maxLength = 1;
        
        for (int i = 0; i < nums.length; i++) {
            lis[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, lis[i]);
        }
        
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("طول أطول تسلسل تصاعدي هو: " + lengthOfLIS(nums));
    }
}

5. الحل في C

#include <stdio.h>

int lengthOfLIS(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int lis[numsSize];
    for (int i = 0; i < numsSize; i++)
        lis[i] = 1;

    int maxLength = 1;
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
            }
        }
        if (maxLength < lis[i])
            maxLength = lis[i];
    }

    return maxLength;
}

int main() {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("طول أطول تسلسل تصاعدي هو: %d\\n", lengthOfLIS(nums, numsSize));
    return 0;
}