A question from interview at Microsoft שאלה מראיון במייקרוסופט: נתונה סדרה של מספרים חיובים ושליליים מובטח לפחות מספר חיובי אחד (הנתון הזה לא באמת משנה את האלגוריתם) צריך למצוא תת סדרה בעלת הסכום המקסימלי (להחזיר את אינדקס ההתחלה ואינדקס הסיום של תת הסדרה) פתרון: עוברים על הסדרה רק פעם אחת מחזיקים 4 פרמטרים, ומעדכנים אותם לאחר קריאת כל איבר: - אינדקס התחלה של תת הסדרה המקסימלית כרגע - אינדקס הסיום של תת הסדרה המקסימלית כרגע - סכום התת סדרה המקסימלית כרגע - הסכום עד כה מתחילים לסכום את האברים ברצף, וכל פעם בודקים מה הסכום שהתקבל ומבצעים החלטה (האם להמשיך לסכום או להתחיל לסכום מחדש). אם התקבל סכום שלילי (או סכום הקטן מ"סכום התת סדרה המקסימלית כרגע") אז נעזוב את מה שסכמנו עד כה ונתחיל לסכום מחדש