... של 100 או של 1000. (0,0,100,0,0,0) (0,0,1000,0,0,0) מה יקרה במקרה כזה? כמה מים ייאגרו? תשובה: 0. או במילים אחרות, אנחנו יודעים
בוודאות, שכל עמוד בודד בכל גובה, לא יאגור בתוכו מים. שזה גם נשמע הגיוני. כי כדי לאגור מים צריך 2 עמודים שיחזיקו ביניהם את המים. עכשיו כדי לנסות להבין את החוקיות של גובה ... 1. נבדוק מה הגובה של העמוד הגבוה ביותר שנמצא מצד שמאל שלו. ונראה שזה העמוד הראשון שהוא בגובה של 3. וזה בעצם אומר, שאנחנו יודעים
בוודאות, שמצד שמאל של העמוד השני שלנו, יש עמוד בגובה של 3. דהיינו, אנחנו יודעים
בוודאות שלא משנה מה, מפלס המים לא יהיה יותר גבוה מ 3. אבל האם אנחנו יכולים לדעת
בוודאות שמפלס המים במיקום של העמוד השני, יהיה 3? אולי הוא יהיה 2 או 1 או אולי אפילו 0? איך נדע את זה? אז במה זה תלוי? לשם כך נצטרך לבדוק את הגובה של העמודים שנמצאים בצד ... שהגובה שלו הוא 3 או יותר, דהיינו, שהגובה שלו הוא זהה או גדול מהגובה של העמוד הגבוה ביותר השמאלי ביותר, הרי שאנחנו יכולים לדעת
בוודאות שגובה מפלס המים יהיה 3 ולא יותר. לא משנה מה. כי בסוף, המים מוגבלים לגובה של העמוד הנמוך ביותר מבין 2 העמודים הגבוהים ביותר. דהיינו, במקרה שלנו, אם נסתכל לצד ימין של ... השני, הרי שנוכל לראות עמודים גבוהים יותר מ 3. וזה בעצם אומר, שמפלס המים במיקום 2, יהיה לא יותר גבוה מ 3. ואנחנו יודעים את זה
בוודאות, גם בלי לדעת מה הגובה הגבוה ביותר מצד ימין, של העמוד שנמצא במיקום השני. או במילים אחרות, כאשר אנחנו מוצאים את הגובה של העמוד הגבוה ביותר, מצד 1 כלשהו, צד ימין או ... 1. נבדוק מה הגובה של העמוד הגבוה ביותר שנמצא מצד שמאל שלו. ונראה שזה העמוד הראשון שהוא בגובה של 3. וזה בעצם אומר, שאנחנו יודעים
בוודאות, שמצד שמאל של העמוד השני שלנו, יש עמוד בגובה של 3. דהיינו, אנחנו יודעים
בוודאות שלא משנה מה, מפלס המים לא יהיה יותר גבוה מ 3. אבל האם אנחנו יכולים לדעת
בוודאות שמפלס המים במיקום של העמוד השני, יהיה 3? אולי הוא יהיה 2 או 1 או אולי אפילו 0? איך נדע את זה? אז במה זה תלוי? לשם כך נצטרך לבדוק את הגובה של העמודים שנמצאים בצד ... שהגובה שלו הוא 3 או יותר, דהיינו, שהגובה שלו הוא זהה או גדול מהגובה של העמוד הגבוה ביותר השמאלי ביותר, הרי שאנחנו יכולים לדעת
בוודאות שגובה מפלס המים יהיה 3 ולא יותר. לא משנה מה. כי בסוף, המים מוגבלים לגובה של העמוד הנמוך ביותר מבין 2 העמודים הגבוהים ביותר. דהיינו, במקרה שלנו, אם נסתכל לצד ימין של ... השני, הרי שנוכל לראות עמודים גבוהים יותר מ 3. וזה בעצם אומר, שמפלס המים במיקום 2, יהיה לא יותר גבוה מ 3. ואנחנו יודעים את זה
בוודאות, גם בלי לדעת מה הגובה הגבוה ביותר מצד ימין, של העמוד שנמצא במיקום השני. או במילים אחרות, כאשר אנחנו מוצאים את הגובה של העמוד הגבוה ביותר, מצד 1 כלשהו, צד ימין או ... העמוד הימני ביותר, העמוד במיקום 20 שהגובה שלו הוא 6. וננסה להבין מה אנחנו יכולים להסיק מכך? האם יש משהו שאנחנו יכולים להסיק מכך
בוודאות? אז התשובה היא, שאולי כן. כי בעצם אנחנו יודעים שבמיקום 20, העמוד הגבוה ביותר הוא בגובה של 6. דהיינו, אנחנו כבר יכולים לדעת
בוודאות, שלא משנה מה, גובה המים במיקום 20, לא יהיה גבוה יותר מ 6. כי זה העמוד הגבוה ביותר שנמצא בצד ימין. אבל האם גובה המים יהיה 6 או פחות מ 6, איך נדע? זה כמובן תלוי בגובה של העמודים שנמצאים מצד שמאל של העמוד הימני ביותר. ואני אדייק, שבפועל
בוודאות שלא יהיו מים כלואים, לא במיקום הראשון ולא במיקום האחרון, בכל תרחיש. כי המים הכלואים, חייבים להיות בין 2 עמודים כלשהם. אבל כרגע לצורך הניתוח, אני מתעלם מזה כרגע ... והאחרון, כאילו הם מיקומים רגילים. אז בעצם מכך שאנחנו יודעים שבצד ימין, במיקום 20, הגובה הגבוה ביותר הוא 6, הרי שאנחנו יודעים
בוודאות שלא יהיו שם מים יותר מגובה של 6. אבל אולי יהיו שם פחות מים בגובה יותר נמוך? אז הרי שכבר יש לנו וודאות חלקית כלשהי. אבל עדיין אין אפשרות להתקדם איתה למסקנה וודאית כלשהי. אז נסתכל על הנקודה הראשונה מצד שמאל, העמוד הראשון, שהוא בגובה של 3. האם מכך אנחנו יכולים להסיק משהו
בוודאות? התשובה היא, שכן! כי אנחנו יודעים שהעמוד הגבוה ביותר מצד שמאל, דהיינו, העמוד הראשון הוא בגובה 3. ולכן אנחנו יודעים
בוודאות שגובה המים לא יהיה יותר גבוה מ 3. אבל האם הוא יהיה אולי פחות מ 3? התשובה היא שלא. הוא יהיה בדיוק 3. ולמה? כי אנחנו יודעים גם שמצד ימין של המיקום הראשון, יש עמוד ... העמוד הימני ביותר כנל. או במילים אחרות, מכך שאנחנו יודעים שהעמוד השמאלי ביותר, הוא 3 והעמוד הימני ביותר הוא 6, הרי שאנחנו יודעים
בוודאות, שבמיקום השמאלי הראשון הגובה יהיה בדיוק 3. ולגבי העמוד הימני, אנחנו לא יודעים עדיין מה יהיה הגובה המדוייק. כי הוא אומנם לא יהיה יותר מ 6, אבל אולי הוא יהיה 5 או אולי 4. למרות שאנחנו כבר יודעים
שבוודאות הוא יהיה לפחות 3. דהיינו, לגבי מיקום 1 השמאלי ביותר, אנחנו יודעים שגובה המים
בוודאות הוא 3. לגבי המיקום 20 הימני ביותר, אנחנו יודעים שגובה המים יהיה בין 3 לבין 6. לא פחות מ 3 ולא יותר מ 6. וכך הגענו לפתרון הבא: ובלי קשר אנחנו יודעים, שלא משנה מה, ... הראשון מצד שמאל, בלי לרוץ אפילו פעם אחת על כל הרשימה, אלא מספיק לדעת מה הערך של העמוד הימני ביותר ושל השמאלי ביותר, כדי לפתור
בוודאות את הקצה השמאלי ביותר או הימני ביותר, כנל. אז בעצם הנקודה הוודאית ביותר כרגע, היא מיקום מספר 1, שבו אנחנו יודעים
בוודאות את גובה מפלס המים ואת כמות המים הכלואים. אז עכשיו נעבור לנקודה הקרובה ביותר, לנקודה במיקום מספר 2, שהגובה שם הוא 1. ונשאל, האם יש משהו שאנחנו יכולים לדעת שם
בוודאות? והתשובה היא, שכן! כי
בוודאות שבמיקום השמאלי של המיקום השני, דהיינו, במיקום הראשון,
בוודאות שגובה מפלס המים הוא 3. ובמיקום השני גובה העמוד הוא 1. דהיינו, גובה העמוד הוא לא גבוה יותר מגובה מפלס המים שנמצא בצד שמאל. ולכן גם במיקום 2, גובה מפלס המים, יהיה
בוודאות 3. וכך הגענו לכאן. וכך נמשיך גם למיקום מספר 3 ונקבל את התוצאה הזאת: ועכשיו נעבור למיקום מספר 4, שבו העמוד הוא בגובה של 7. אז אנחנו מבינים שמפלס המים כבר לא חייב ... לא יותר מ 7 ולא פחות מ 6. דהיינו, או 6 או 7. אבל אין לנו וודאות לגבי מה יהיה גובה מפלס המים במיקום 4. אבל אנחנו כן יכולים לדעת
בוודאות מה יהיה גובה מפלס המים במיקום 20. כי יש שם עמוד בגובה 6 ומצד שמאל שלו יש עמוד בגובה 7. דהיינו, מפלס המים במיקום 20, יהיה 6. כך: אז כרגע יש לנו וודאות לגבי מיקום 20, ויש לנו וודאות חלקית לגבי מיקום 4. ולכן נמשיך במיקום 19, וננסה לראות האם ומה אפשרי להסיק שם. ושם גובה המים הוא 4, דהיינו,
בוודאות שהמפלס יהיה שם 6. וכמות המים הכלואים תהיה 2 כך: ואז נמשיך למיקום מספר 18 ונגיע לזה: ועכשיו נעבור למיקום מספר 17, ונראה שיש שם עמוד בגובה של 10. דהיינו, נוכל לדעת
בוודאות, שמפלס המים שם לא יהיה יותר מ 10, והוא גם לא יהיה פחות מ 7, שזאת הנקודה הגבוה ביותר שידועה לנו עד כה מצד שמאל. ולכן כרגע אנחנו יכולים לדעת שהמים במיקום 17, יהיו בין 7 לבין 10. אבל נוצרה לנו וודאות, לגבי מיקום 4. שיש שם עמוד בגובה של 7 ומצד ימין יש במיקום 17 עמוד בגובה 10. ולכן
בוודאות נוכל לדעת שבמיקום 4, יש מים בגובה 7. לא יותר ולא פחות. וכך הגענו לכאן: וכך נמשיך הלאה עד שנפתור את כל התרגיל, כך: אז איך בעצם פתרנו את השאלה? קודם כל חילקנו לחלקים, ...