Reach N
Practice
5 (4 votes)
Algorithms
Introduction to dynamic programming 2
Dynamic programming
Problem
80% Success 509 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code
You are given an array \(a\) consisting of \(n\) integers. In one move, you can jump from your current index \(i\) to some index \(j\) if,
- \(i < j\)
- \(j \leq n\)
- \((j - i) = (2 ^ K)\) (where \(K \ge 0\)) (i.e difference between the current index and next index should be equal to some power of \(2\))
You will start from index \(1\) and your task is to reach index \(n\) maximizing the sum of the path.
Sum of the path:
Let the indices that you go through while going from index \(1\) to index \(n\) are \(1, i_2, i_3, ... , n\). So, sum of the path here is equal to \(a[1] + a[i_2] + a[i_3] + ... + a[n]\).
Input Format:
- The first line contains one integer \(T\) \(-\) the number of test cases. Then \(T\) test cases follow.
- The first line of each test case contains a single integer \(n\) \(-\) the number of elements in array \(a\).
- The second line of each test case contains \(n\) integers \(-\) the elements of the array \(a\).
Output Format:
For each test case, output in a seperate line:
Maximum sum of path if you start from index \(1\) and stop at index \(n\).
Constraints:
- \(1 \leq T \leq 10^5\)
- \(1 \leq N \leq 10^6\)
- \(-10^9 \leq a_i \leq 10^9\) for all \(i\) from \(1\) to \(n\).
- It is guaranteed that sum of \(N\) over all test cases doesn't exceed \(10^6\).
Submissions
Please login to view your submissions
Similar Problems
Points:30
1 votes
Points:30
Tags:
mediumDynamic programmingArrays2dIntroduction to Dynamic Programming-2AlgorithmsMediumDynamic Programming
Points:30
8 votes
Tags:
Introduction to Dynamic Programming-2AlgorithmsMediumDPDynamic Programming
Editorial