(solved) Can you help me to fix this error?

Question

I was trying to find the Maximum sum such that no two elements are adjacents, also the Indices of the chosen elements. But the output is not correct, can you solve the problem?

https://code.sololearn.com/cHLw7Lm7L83A/?ref=app

Answer 1

Here you go. Recursive was easier but definitly horrid runtime. Reminds me of Fibonacci so probably closer to 2^n.
Rules that can be assumed that give recursive form.
-either we take the first or second element
-if we take one then we do not take the following element
-we must take one of the two that follows

For sure will run in O(n) in for loop version
Seems to work. You'll have to add index stuff. Your logic is off on your inclusive exclusive.
Gave 20 instead of 18 on first case u gave.

Pretty much optimization is if you write these out, you see you get duplicates based on sums so far.

[a,b,c,d,e,f,g,...]
a -> ac -> ace .. g
-> acf
-> ad -> adf
-> adg
- assume a > b
b -> bd < ad
-> be < ace

*Would have posted last night but got something went wrong error.
Positive values only :)

So code: I got rid of long and made it ints
https://code.sololearn.com/caZ8lhi2WifY/?ref=app

Answer 2

This task is more difficult than it looks like. I think 1 for loop is not enough.

Answer 3

https://code.sololearn.com/cu1zGlsoIUSA/?ref=app
I think you sum is also wrong
I changed a little bit but it didn't helped

Answer 4

Abol
Sure!!
Given an array of N, each element of the array represents the gain. I should find the maximum amount of gain.
No two elements are adjacents.

Answer 5

Abol
Sure.
N = 6
V=[3, 2,5,6,6,9]
Max gain=18
Indices [1,4,6] one based

Answer 6

The expected output is 2,5
But it gives more Indices.

Answer 7

Thank you Stefanoo
The function works now but the result should be 9 not 11. And the Indices of the element should be in the output.

5+3+1

Answer 8

Stefanoo
I appreciate your help!
I have been trying to fix it the last few days but I couldn't.
I don't know how to solve this!

Answer 9

The algorithm must be less than O(N^2)
So that what I thought of.

Answer 10

Thank you so much Abol
I really appreciate your help!!
I just want to know why the algorithm in the example is outputting
[0,3]->(1+4=5)
While the Indices can be
[1,3] - >(2+4=6) and they are not adjacents also.

Answer 11

Abol
Thanks ALLAH of course!!

Answer 12

Javadev
So amazing!!
Thank you so much, I have been trying that I lost hope!
I also understand the two algorithms, thank you for the clarification!!

Answer 13

probably you could do like before, but instead with 2 lists.
one for inclusive index and one for exclusive index.
swap those math.max statements to be if .. else statements and add index to it like before.
where before we were copying the inclusive value to exclusive or vice-versa, you will have to copy your index list to each other.

adding console.writeline statements during index copy will give hints what could be improved. probably won't be efficient lists copies this way. don't have time to think more about it until tomorrow, so best i can think of currently.

Answer 14

also: to deal with negatives. you could make those its own loop.
where if its negative, you replace with zero. and keep track of largest.
if largest is <= 0. then you are done. just return it and index.

this kind of means in current code. you could skip doing anything if value is 0. clearly 0's can be ignored from your sum and index since they don't add anything to sum.

Answer 15

Javadev
I am so grateful for your help!!
I will follow your steps and post the code as soon as I finish.
Thank you a lot, this was so helpful!!

Answer 16

Abol
For example,
N =5, V=[5,2,1,3,1]
Max gained =8
Indices [1,4]. One based

Max gain is maximum sum of the array element chosen.
In this example 5+3=8 is the maximum sum of chosen array elements such that no two elements are adjacents.

Answer 17

Abol congrats!!
I will trace it now.
Thank you for helping me!!

Answer 18

Javadev
Could you please give me a hint on how to get the Indices and I will do it!!