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,

  1. \(i < j\)
  2. \(j \leq n\)
  3. \((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\)
     

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
8 votes
Tags:
Introduction to Dynamic Programming-2AlgorithmsMediumDPDynamic Programming
Points:30
1 votes
Tags:
Introduction to Dynamic Programming-2AlgorithmsDynamic Programming
Points:30
11 votes
Tags:
BitmaskDynamic ProgrammingAlgorithmsApprovedMedium