I'm getting this only partially correct, please help in code

#1

Please help in my code: https://ide.codingblocks.com/s/161280
I’m getting this partially correct. As shown in the hint video, I’m keeping track of two max values (1st and 2nd highest) and for every window every element I’m looking for the highest possible value. I’m not able to find out where it’s getting stuck on…Please help!

#2

Hey I have Checked your solution. You seem to have over complicated it. You simply need to find a max from every k elements and add it to the sum. This can be accomplished using the following very sinple code.

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long> a(n);
    for(auto &i : a)
        cin >> i;
    long maxSum = 0;
    vector<long> dp = a;
    for(int i = k; i < n; i += k) {
        int max_i = i - k, smax_i = -1;
        for(int j = i - k + 1; j < i; j++) {
            if(dp[j] > dp[max_i]) {
                smax_i = max_i;
                max_i = j;
            }
            else if(smax_i == -1 or dp[j] > dp[smax_i]) {
                smax_i = j;
            }
        }
        for(int j = i; j < i + k and j < n; j++) {
			if(a[j] < 0) dp[j] = dp[max_i];
            else if(j - max_i != k) dp[j] = a[j] + dp[max_i];
            else dp[j] = a[j] + dp[smax_i];
            maxSum = max(maxSum, dp[j]);
        }
    }
    cout << maxSum;
}
#3

Thanks for the help. Yes, its a bit complicated, not able to come up with an efficient yet simpler way. I tried running your code, it is giving WA on every case.

#4

Oh! Let me check. I Didn’t check it on the testcases.

#5

Yeah you are right I haven’t considered the second condition |i - j| != k

#6

Yes, I made currMax and nextMax for storing current 1st and 2nd max values in case 1st max is coming at |i-j| == k, I’d use 2nd max for that…and nextMax stores 1st & 2nd max for next window of subarray accordingly.

#7

Hey you can check I have edited the above code and see If this helps you.

#8

Wow, it’s very readable. So you’re finding 1st and 2nd max’s indexes in first inner for loop and then using that to update & maintain the global max value!?

Thanks!

#9

I have read your code also you are using 4 variables for max. currMax[2] and nextMax[2]. I am not sure why have you used 4 varibles for storing the max variables. But I think you have error in updating these variables.
You can check my code to see how to update these variables.

#10

If I have resolved your doubt. Please mark this as resloved and Rate it. :smile: Thank you. :slight_smile:

#11

Thanks. Marked it resolved.