There is an 1-D array with elements {5,30,99,60,5,10}. From this array, 1 sub-sequence is 5, 99 and 10 which sums up to a value of 114. Other sub-sequences sum are lesser than 114. Two elements should not be contiguous in the sub-sequence ie {5, 30 and 60} is not a valid sub-sequence (for this problem). It can be either {5, 99, 5} or {30, 60, 10} etc. The array doesn't contain negative numbers. What approach will be the right way to calculate this maximum sum? I am trying to implement it in C.
4
-
1There is an algorithm for that but is difficult to explain. You can read it herebabaliaris– babaliaris2019-05-19 19:11:34 +00:00Commented May 19, 2019 at 19:11
-
@babaliaris It looks like that algorithm doesn't meet the constraint that the sequence may not be made from adjacent list items.Shawn– Shawn2019-05-19 19:16:14 +00:00Commented May 19, 2019 at 19:16
-
@babaliaris that is for contiguous elements..hago– hago2019-05-19 19:20:26 +00:00Commented May 19, 2019 at 19:20
-
You can modify it to implement them. It might be a difficult task to do but optimization algorithms are hard by their nature. You will need to work that out a lot in order to be able to implement what you are trying to do.babaliaris– babaliaris2019-05-19 19:20:47 +00:00Commented May 19, 2019 at 19:20
Add a comment
|
1 Answer
Recursion is your friend here
Sum is the maximum of
5 + maxSum of {99, 60, 5, 10}
or discard 5 in favor of 30 and
30 + maxSum of {60, 5, 10}
Assuming you do not have any negative numbers, you should use either 5 or 30 and then the remaining sequence. Discarding both of them does not make sense.
