Once upon a time in Time-Land | Solve programming problems on HackerEarth

Once upon a time in Time-Land | Solve programming problems on HackerEarth
In a mystical TimeLand, a person's health and wealth is measured in terms of time(seconds) left. Suppose a person there has 24x60x60 = 86400 seconds left, then he would live for another 1 day. A person dies when his time left becomes 0. Some time-amount can be borrowed from other person, or time-banks. Some time-amount can also be lend to another person, or can be used to buy stuffs.
Our hero Mr X, is in critical condition, has very less time left.
Today's the inaugural day of a new time-bank. So they are giving away free time-amount worth 1000 years.
Bank released N slips, A[1], A[2], .... A[N]. Each slip has a time-amount(can be +ve as well as -ve).
A person can pick any number of slips(even none, or all of them, or some of them) out of the N slips. But bank introduced a restriction, they announced one more number K. Restriction is that, if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]. It means there should be a difference of atleast K between the indices of slips picked.
Now slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible with the given restriction.
If you predict the maximum positive sum possible, then you win.
Mr X has asked for your help. Help him win the lottery, and make it quick!
Input Format:
First line of the test file contains single number T, the number of test cases to follow.
Each test case consists of two lines.
First line contains two numbers N and K , separated by a space. Second line contains the N numbers A[1], A[2] ..... A[N] separated by space.
Output Format:
For every test case, output in a single line the maximum positive sum possible, that is output for the case.

Solution :

• maximum sum is to be found, so we ignore negative integers.
• If we select ith index, next index to be selected will be (i+K+1) th index.

Lets take a DP approach. We are going to construct an array in which all the indexes represent maximum possible sum upto that index following the above rules.

• Take an array of size N. SUM(0....N-1)
• Initialize all elements of that array to zero.
• For an array with just 1 element, maximum sum would be that element or zero, SUM[0] = max(0, first element)
• Then we iterate from index 1 to N-1.
  • If integer at current index is negative we take the sum upto previous index as the maximum sum.
  • If current index is less than or equal to K, i.e. we are still trying to pick the first element optimally, we pick the maximum(integer at current index, sum upto previous index).
  • If Current index is greater than K, we select the maximum(sum upto previous index , integer at current index + sum upto [current index - K - 1]).
• SUM[N-1] will be our answer.

    for(;T--;)
    {
        int N,K;
        cin >> N >> K;

        vector<long long> A(N), SUM(N,0);

        for (int i = 0; i < N; ++i)
            cin >> A[i];

        SUM[0] = max(A[0],0ll);
        for (int i = 1; i < N; ++i)
        {
            if(A[i] < 0)
                SUM[i] = SUM[i-1];
            else if(i-K-1 < 0)
                SUM[i] = max(SUM[i-1],A[i]);
            else
                SUM[i] = max(SUM[i-1],A[i]+SUM[i-K-1]); 
        }
        cout << SUM[N-1] << "\n";
    }

Read full article from Once upon a time in Time-Land | Solve programming problems on HackerEarth