حل بتعقيد O(n) لمسألة الفارق المطلق الأقصى في المصفوفة

بدأت بعض الأسئلة البرمجية تحول نحو مستويات أعلى من التحدي، حيث يتعين عليك الآن التفكير بطرق أكثر كفاءة لحلها. لقد تحدثت عن حل بتعقيد O(n^2) حيث تستخدم حلقتين تضمان التحقق من كل زوج ممكن من العناصر في المصفوفة. لكن هل يمكن تحسين هذا الأمر ليصبح بتعقيد O(n)؟

لنلقِ نظرة عميقة على الوظيفة f(i, j) التي تقيس الفارق المطلق بين قيمتين في المصفوفة مع الفارق المطلق بين المواقع التي يتواجدون فيها. إذا نظرنا إلى هذه الوظيفة بعناية، سنلاحظ أنه يمكننا تقسيمها إلى أربعة جزئين:

1. |A[i] – A[j]| حيث يتم قياس الفارق المطلق بين القيمتين في المصفوفة.
2. |i – j| حيث يتم قياس الفارق المطلق بين المواقع التي يتواجدون فيها.

بما أننا نركز على قيمة مطلقة، فإن الفرق بين القيمتين يكون إما إيجابيًا أو سالبًا. لذا، يمكننا أن ننظر إلى هذه القيمتين على أنهما يُمثِّلان زوجًا من الأرقام، وهنا يأتي دور العمليات الحسابية للتحقق من القيمة المطلقة للفارق بينهما.

تساوي الحالات الممكنة لعملية الطرح الفرق بين القيمتين بين أرقام متطابقة، أو بين أرقام مختلفة. وبالمثل، تساوي الحالات الممكنة لعملية الطرح الفارق بين المواقع بين أرقام متطابقة، أو بين أرقام مختلفة.

باستخدام هذه الفكرة، يمكننا الآن تحويل الوظيفة f(i, j) إلى وظيفة أكثر بساطة:

1. إيجاد القيمة القصوى لـ |A[i] – A[j]| عن طريق اختيار القيمة القصوى لـ A[i] والقيمة الصغرى لـ A[j]، ثم اختيار القيمة الصغرى لـ A[i] والقيمة القصوى لـ A[j]. يمكن تحقيق ذلك ببساطة عن طريق إيجاد الفارق بين أقصى قيمة وأدنى قيمة في المصفوفة.
2. إيجاد القيمة القصوى لـ |i – j|، وهو ببساطة الفارق بين أقصى وأدنى المواقع.

باستخدام هذه الأفكار، يمكننا الآن كتابة حل بتعقيد O(n) بدلاً من O(n^2). هذا يعني أنه يمكننا حل المشكلة بشكل أكثر كفاءة، وتجنب الوقوع في فخ الزمن الطويل الذي يأتي مع الحلول ذات التعقيد العالي.

بالطبع، سأواصل التوسع في المقال لشرح الحل الجديد بالتفصيل.

بعد فهم الطريقة التي يمكن من خلالها تحليل الوظيفة f(i, j) إلى جزئين مستقلين، يمكننا الآن البدء في تطبيق هذا الفهم على الحل بشكل عملي.

أولاً، لنبدأ بحساب القيمة القصوى لـ |A[i] – A[j]|. يمكننا القيام بذلك ببساطة عن طريق إيجاد الفارق بين أقصى قيمة وأدنى قيمة في المصفوفة A. هذا الفارق سيمثل القيمة القصوى لفارق القيم بين العناصر في المصفوفة.

ثانياً، سنقوم بحساب القيمة القصوى لـ |i – j|. هذا يعني أننا ببساطة نقوم بطرح أدنى قيمة الموقع من أقصى قيمة الموقع في المصفوفة، وبالتالي نحصل على الفارق الأقصى بين المواقع.

ثالثاً، بعد حساب كلتا القيمتين القصوى، يكفينا الآن جمعهما معاً للحصول على القيمة القصوى النهائية للوظيفة f(i, j).

باستخدام هذا النهج، نستطيع الآن كتابة الحل بشكل مباشر بدون الحاجة إلى الحلقتين التي زادت من تعقيد الحل في النسخة السابقة.

سأقوم الآن بتقديم الحل بالشكل التالي:

javaCopy code
public class Solution {
    public int maxArr(ArrayList A) {
        int maxDiffValue = Integer.MIN_VALUE;
        int minDiffValue = Integer.MAX_VALUE;
        int maxDiffIndex = Integer.MIN_VALUE;
        int minDiffIndex = Integer.MAX_VALUE;

        for (int i = 0; i < A.size(); i++) {
            int currentValue = A.get(i);
            int currentDiff = currentValue + i;
            int currentNegDiff = currentValue - i;

            maxDiffValue = Math.max(maxDiffValue, currentDiff);
            minDiffValue = Math.min(minDiffValue, currentDiff);
            maxDiffIndex = Math.max(maxDiffIndex, currentNegDiff);
            minDiffIndex = Math.min(minDiffIndex, currentNegDiff);
        }

        int diff1 = maxDiffValue - minDiffValue;
        int diff2 = maxDiffIndex - minDiffIndex;

        return Math.max(diff1, diff2);
    }
}

باستخدام هذا الحل، يمكننا الآن حساب القيمة القصوى للوظيفة f(i, j) بتعقيد O(n)، مما يجعل الحل أكثر كفاءة وسرعة في حالة المصفوفات الكبيرة. هذا يعكس الفهم العميق للمشكلة والتفكير الإبداعي في طرق تحسين الأداء.