Long Jumps (Codeforces 1472C)
Tags: DP, graphs

Polycarp found under the Christmas tree an array $$$a$$$ of $$$n$$$ elements and instructions for playing with it:   At first, choose index $$$i$$$ ($$$1 \leq i \leq n$$$) — starting position in the array. Put the chip at the index $$$i$$$ (on the value $$$a_i$$$).  While $$$i \leq n$$$, add $$$a_i$$$ to your score and move the chip $$$a_i$$$ positions to the right (i.e. replace $$$i$$$ with $$$i + a_i$$$).  If $$$i > n$$$, then Polycarp ends the game. For example, if $$$n = 5$$$ and $$$a = [7, 3, 1, 2, 3]$$$, then the following game options are possible:   Polycarp chooses $$$i = 1$$$. Game process: $$$i = 1 \overset{+7}{\longrightarrow} 8$$$. The score of the game is: $$$a_1 = 7$$$.  Polycarp chooses $$$i = 2$$$. Game process: $$$i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$$$. The score of the game is: $$$a_2 + a_5 = 6$$$.  Polycarp chooses $$$i = 3$$$. Game process: $$$i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$$$. The score of the game is: $$$a_3 + a_4 = 3$$$.  Polycarp chooses $$$i = 4$$$. Game process: $$$i = 4 \overset{+2}{\longrightarrow} 6$$$. The score of the game is: $$$a_4 = 2$$$.  Polycarp chooses $$$i = 5$$$. Game process: $$$i = 5 \overset{+3}{\longrightarrow} 8$$$. The score of the game is: $$$a_5 = 3$$$. Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way.

Input: The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output on a separate line one number — the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from $$$1$$$ to $$$n$$$ in such a way as to maximize his result.

Note: The first test case is explained in the statement.In the second test case, the maximum score can be achieved by choosing $$$i = 1$$$.In the third test case, the maximum score can be achieved by choosing $$$i = 2$$$.In the fourth test case, the maximum score can be achieved by choosing $$$i = 1$$$.

Sample Inputs:
4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1

Sample Outputs:
7
6
1000
5

Solution (Python):
import math
import cmath
import string

def sieve(n):
    l = [0] * (n + 1)
    l[0] = l[1] = 1
    for i in range(2, int(n ** 0.5) + 1):
        if not l[i]:
            for j in range(i * i, n + 1, i):
                l[j] = 1
    return [i for i in range(n + 1) if l[i] == 0]

def sieveOptemised(n, prime):
    l = [0] * (n + 1)
    l[0] = l[1] = 1
    for i in range(2, n):
        if not l[i]:
            prime.append(i)
        for j in range(len(prime)):
            if i * prime[j] >= n:
                break
            l[i * prime[j]] = 1
            if i % prime[j] == 0:
                break

def XOR(n):
    return [n, 1, n + 1, 0][n % 4]

def isprime(n):
    return all([False for i in range(2, n) if n % i == 0]) and (not n < 2)

def searchBinary(lis, l, r, e):
    ans = 0
    while l <= r:
        m = (l + r) // 2
        if lis[m][0] > e:
            r = m - 1
        else:
            l = m + 1
            ans = l
    return ans

def f(l, i, j, n, m):
    c = l[i][j]
    i1 = i
    j1 = j
    i2 = i
    j2 = j
    i3 = i
    j3 = j
    i4 = i
    j4 = j
    while i1 > 0 and j1 > 0:
        i1 -= 1
        j1 -= 1
        c += l[i1][j1]
    while i2 < n - 1 and j2 < m - 1:
        i2 += 1
        j2 += 1
        c += l[i2][j2]
    while i3 > 0 and j3 < m - 1:
        i3 -= 1
        j3 += 1
        c += l[i3][j3]
    while i4 < n - 1 and j4 > 0:
        i4 += 1
        j4 -= 1
        c += l[i4][j4]
    return c

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def binarySearch(lis, l, r, e):
    while l <= r:
        m = (l + r) // 2
        if lis[m] == e:
            return 1
        elif lis[m] > e:
            r = m - 1
        else:
            l = m + 1
    return 0

def isSqrt(n):
    for i in range(1, int(n ** 0.5) + 2):
        if i * i == n:
            return True
    return False
result = list(string.ascii_lowercase)
alpha = {}
for i in range(26):
    alpha[result[i]] = i + 1
import random

def fermatTesting(n, k):
    if n == 1 or n == 4:
        return False
    elif n == 2 or n == 3:
        return True
    for i in range(k):
        a = random.randint(2, n - 2)
        if pow(a, n - 1, n) != 1:
            return False
    return True

def check_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(n)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

def mex(l):
    ll = l.copy()
    ll.sort()
    for i in range(len(l)):
        if i != ll[i]:
            return i
    return len(l)
aa = []
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    ans = l.copy()
    for i in range(n - 1, -1, -1):
        if i + l[i] < n:
            ans[i] += ans[i + l[i]]
    aa.append(max(ans))
for i in aa:
    print(i)

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
from collections import Counter, defaultdict

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def main():
    length = inp()
    array = inlt()
    for i in range(length - 1, -1, -1):
        newPlace = i + array[i]
        if newPlace < length:
            array[i] += array[newPlace]
    print(max(array))
if __name__ == '__main__':
    t = inp()
    for _ in range(t):
        main()

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
from collections import Counter, defaultdict

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def main():
    length = inp()
    array = inlt()
    for i in range(length - 1, -1, -1):
        if i + array[i] < length:
            array[i] = array[i] + array[i + array[i]]
    print(max(array))
if __name__ == '__main__':
    t = inp()
    for _ in range(t):
        main()