שלום!
(אני כותב ב-C++)
יש לי מערך דו מימדי (לא ממוין), אני צריך למצוא את התת-מערך הכי גדול, שאיבריו בסדר עולה כלומר כל תא קטן או שווה לתא שאחריו בשורה, והתא האחרון בשורה גם כן קטן מהאיבר הראשון בשורה הבאה שלו (של התת מערך).
דוגמא:
זה המערך:
1 0 2 4 7
5 3 2 1 8
13 11 9 7 2
30 28 14 12 1
וזה תת המערך הכי גדול המקיים את התנאי (מונוטוני עולה).
3 2 1
11 9 7
28 14 12

כל עיצה תעזור.. תודה מראש!!

אתה יכול להסתכל על הבעיה כאילו קיבלת מערך חד מימדי של מספרים לא ממוינים ואתה רוצה לקבל תת סדרה עולה שערכיה מקסימלים

(כוון שכל מערך דו מימדי ניתן לרשום כמערך חד ממדי)
זאת בעיה שניתנת לפתירה רקורסיבית אם אתה רוצה עוד עזרה תגיד....

אוקיי, אבל נגיד שמצאתי בשורה הראשונה ששלושת התאים השמאליים הם מקיימים את התנאי וגם 3 תאים, זה הכי הרבה בשורה הראשונה. אם אני ילך לשורה השניה אני יכול למצוא 3 תאים שמקיימים את התנאי אבל נמצאים בצד ימין (לא מתחת שלושת הקודמים..).
אז מה למה אתה מתכון שאני צריך להתכל על זה כמערך חד מימדי?
תודה רבה!!

סליחה לא התייחסתי לעובדה שאתה צריך להחזיר מערך מסוג n X n
טעות שלי...

סליחה אבל לא הבנתי.

האם אפשר\צריך להחזיר רק תוצאה אחת? משתמע ממה שכתבת שצריך להחזיר רק מערך אחד חד-מימדי ("אני צריך למצוא את התת-מערך הכי גדול").

ציטוט:

וזה תת המערך הכי גדול המקיים את התנאי (מונוטוני עולה). 3 2 1

למה לא כתבת בפיתרון\במערך הראשון שהוא צריך להיות:

קוד:

1 2 3 5

הרי 3 קטן מ-5, ו-5 קטן מ-7 שנמצא בשורה הבאה, ולכן גם המספר 5 צריך להיות בפיתרון של המערך הראשון.

יפה, זה בדיוק הבעיה! כל זה:
3 2 1
11 9 7
28 14 12
זה תת מערך אחד (מסדר 3x3) שנמצא במערך הגדול....
כי אני צריך תת מערך הכי גדול וזה יכול להיות גם מערך דו מימדי...
אגב, זה לא חייב להיות מסדר n x n.
תודה רבה לכל העוזרים!!!

עדיין לא הבנתי למה לא הוספת את ה-5 לשורה הראשונה ... :/

נניח זה המערך הדו-מימדי שקיבלתי:

קוד:

1 0 2 4 7
5 3 2 1 8
13 11 9 7 2
30 28 14 12 1

למה שאני לא אספק לך תוצאה כזו:

קוד:

0 2 4 
1 8
13
30

כאשר כל התשובה הנ"ל זה מערך דו-מימדי, וכל שורה בפני עצמה מייצגת מערך.

האם ניתן שבכל המקרים האפשריים, אחזיר כתשובה מערך חד-מימדי עם כל התוצאות?

בכל אופן... אנסה לתת לך כיוון מחשבה למרות שאני לא בטוח שהבנתי:

קודם כל תבדוק מהו האיבר הראשון בשורה השנייה, כלומר מה הגודל שלו.
אח"כ תסרוק את השורה הראשונה מהאיבר האחרון אל האיבר הראשון, ותנסה למצוא את האיבר ששווה\קטן מהאיבר הראשון בשורה השנייה. ואז תבדוק אם האיברים שלפניו (לפניו מבחינת המיקום במערך \ אינדקס) קטנים ממנו. אם כן אז יש לך תוצאה בשורה אחת, אם לא אז תמשיך לסרוק את השורה...

וכן הלאה לגבי השורות האחרות.

תתבונן:
"בסדר עולה כלומר כל תא קטן או שווה לתא שאחריו בשורה, והתא האחרון בשורה גם כן קטן מהאיבר הראשון בשורה הבאה שלו (של התת מערך)."
קודם כל אני צריך תת מערך שיהיה עם מספר עמודות שווה בכל שורה. כלומר לא יכול להיות תת מערך עם 3 איברים בשורה הראשונה 5 איברים בשורה השניה ו-8 איברים בשורה השלישית... בכל השורות חייב להיות אותו מס' של איברים.
חוץ מזה צריך שהאיבר האחרון בשורה הראשונה יהיה יותר קטן מהאיבר הראשון בשורה השניה זה כאילו המשך...

ציטוט:

תתבונן: "בסדר עולה כלומר כל תא קטן או שווה לתא שאחריו בשורה, והתא האחרון בשורה גם כן קטן מהאיבר הראשון בשורה הבאה שלו (של התת מערך)."

איזה מוזר , חשבתי שכתבתי תוצאה אחרת...


אוקי אז בנוגע לפיתרון:

תיעזר במה שכתבתי בהודעתי האחרונה:

ציטוט:

קודם כל תבדוק מהו האיבר הראשון בשורה השנייה, כלומר מה הגודל שלו. אח"כ תסרוק את השורה הראשונה מהאיבר האחרון אל האיבר הראשון, ותנסה למצוא את האיבר ששווה\קטן מהאיבר הראשון בשורה השנייה. ואז תבדוק אם האיברים שלפניו (לפניו מבחינת המיקום במערך \ אינדקס) קטנים ממנו. אם כן אז יש לך תוצאה בשורה אחת, אם לא אז תמשיך לסרוק את השורה...

אבל במקביל לנ"ל, תיצור מערך דו-מימדי (נקרא לו arr_info) בגודל מספר השורות שיש לך במערך ה-input, כאשר כל תת-מערך אצלו הוא בגודל 2 איברים - האיבר הראשון מצביע על ה-offset של המספר הראשון בסידרה, והאיבר השני מצביע על גודל הסידרה (כמה איברים מתאימים מצאת עבור שורה ספציפית, בהתאם לחוקיות הנדרשת בתרגיל).

אחרי שתמלא את arr_info בנתונים, תחפש בו את הערך של גודל הסידרה הקטן ביותר, ובהתאם לכך תשלוף את הנתונים החל מה-offset המתאים בכל תת-מערך שנמצא במערך ה-input.

עריכה:

אולי זה יעזור להבין טוב יותר:

קוד:

The input - 2 Dimensional array:
7 4 2 0 1
8 1 2 3 5
2 7 9 11 13
1 12 14 28 30

int arr_info[4];

//  arr_info[/* row index */] = {/* offset */, /*  series length */}
arr_info[0] = {NULL, 0} // Because that there's no match in the first row
arr_info[1] = {1, 3}
arr_info[2] = {1, 3}
arr_info[3] = {1, 3}