נתון מערך חד-ממדי a המלא במספרים שלמים.
יש להחזיר את מספר תת-המערכים בתוכו שהם מסודרים בסדר עולה ממש (כלומר ללא מספרים שווים). שימו לב, מדובר על תאים הסמוכים אחד לשני. אורך של תת-מערך מסודר בסדר עולה ממש הוא לפחות 2.
לדוגמה,
a הבא:| 0 | 1 | 2 | 3 | 4 |
| 1 | 2 | 4 | 4 | 5 |
יוחזר הערך 4.
אלו ארבעת תת-המערכים המסודרים בסדר עולה ממש: (1, 2), {1, 2, 4}, {2, 4}, {4, 5}
a הבא:| 0 | 1 | 2 |
| 1 | 3 | 2 |
יוחזר הערך 1. תת-המערך {1, 3}
a הבא:| 0 | 1 | 2 | 3 | 4 |
| 5 | 4 | 3 | 2 | 1 |
יוחזר הערך 0.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
a = [1, 2, 4, 4, 5]
4
הסבר: ארבעת תת-המערכים המסודרים בסדר עולה ממש הם: (1, 2), {1, 2, 4}, {2, 4}, {4, 5}
a = [1, 3, 2]
1
הסבר: תת-המערך היחיד המסודר בסדר עולה ממש הוא: {1, 3}
a = [5, 4, 3, 2, 1]
0
הסבר: אין תת-מערכים המסודרים בסדר עולה ממש.
a = [1, 2, 3, 4, 5]
10
הסבר: כל תת-מערך אפשרי הוא מסודר בסדר עולה ממש.
a = [1, 1, 1, 1]
0
הסבר: אין תת-מערכים המסודרים בסדר עולה ממש.
a = [1, 3, 5, 7, 9]
10
הסבר: כל תת-מערך אפשרי הוא מסודר בסדר עולה ממש.
a = [10, 9, 8, 7, 6, 5]
0
הסבר: אין תת-מערכים המסודרים בסדר עולה ממש.
a = [2, 4, 6, 8, 10, 12]
15
הסבר: כל תת-מערך אפשרי הוא מסודר בסדר עולה ממש.
קלט:
a = [1, 2, 4, 4, 5]
הפלט המבוקש:
4