- Problem 1 You Are Playing A Game Of Hopscotch With These Rules The Plot Consists Of A Row Of N Squares Each With A Num 1 (172.91 KiB) Viewed 70 times
Problem 1 You are playing a game of hopscotch with these rules: The plot consists of a row of n squares, each with a number on it. These numbers are 21, ... , An, where ai > 0 is the number on the di i-th square. You start at square 1 and with each jump you move either two or three squares forward from your current location: that is, from square i you can jump to square i + 2 or square i + 3. You add up the numbers on the squares you jump through, and the person with the largest sum wins. What is the largest sum you can get? Design an O(n) algorithm for this problem. For example, for input 1,5,2,3,6, 1,8, you can jump 1,-, 2, -,6,-,8, with total sum 17, which is the largest possible sum. For input 1,5, 2, 6, 3, 8, 1, the largest sum is 15 (jump sequence 1,-,-,6,-,8,-). 2 > 2 > > >