מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/רשת החומוסיות/שאלה

רשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. $m_1,m_2,\dots m_n$ מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:

1. מסקר שוק, הרשת מעריכה שבבית מספר $m_i$ רווחיה הצפויים יהיו $p_i$ ‏($p_i$ הוא מספר חיובי כלשהו).
2. הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ$k$‏ ($k$ הוא מספר שלם חיובי כלשהו).

תבנית:מבנה תבנית

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