my approach in this question is first adding index of elements of array which have adjacent strictly greater elements in priorityQueue which will prioritize them according to value of elements at that index.so, elements greater than other will be first polled out from queue.then for each element in list i check it is possible to do negation of item or not.
i am unable to solve minimum sum possible part…in start i think by negation of bigger value elemnts will automatically give minimum sum but as from verdict WA i think i am wrong.so, i need help in minimumSum part which i think can be implemented using DP but not able to implement.
Consider the case 3 6 5 6 4 . as per your approach, you would select 3, 5, and 4. After which you would select 5 thereby rejecting 3 and 4 which would have given the better answer. This question does not need greedy approach. DP is the way to go, but there is a O(n) way of doing it also. Check this gfg article https://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/
Some more cases to think on is 4 5 3 5 3 5 4 -> which after removing the unwanted greater elements becomes, {4, 3, 3, 4}, apply the method in the above article to find the maximum sum without adjacent elements (I hope you understand why we don’t need the adjacent elements, otherwise we will end up with a negative contiguous subsequence or subarray).
And if you need the indices, use a linked list. See a sample code here. I used this approach in JAVA and code ran in 1.9s (C++ eq of 0.98s)
Ofcourse this approach is only for subarrays where sum of alternate elements is greater than the element between them…
so for
1 5 1 1 4 5 3 5 3 5 4
ans is
-1 5 -1 1 -4 5 3 5 3 5 -4
where I call the first 3 elements are “good” and the subarray 4 5 3 5 3 5 4 as “bad”. The above approach is to handle the bad cases because all elements in the “good” sections should be inverted without any second thought.
as well explained by @kukreja_vlk your solution may fail in some cases… Bit masking( It means checking each possible combination) is one of the solution for this , but it would award you only 20 points as its not an efficient approach…hence DP is the solution for this problem… Here is my answer(c++ code) in which I tried to explain my approach which ran in about (0.33) secs…
i have doubt like in ur example {4 5 3 5 3 5 4} if replace 5 with big number like 10 then new example will be {4 10 3 10 3 10 4} which after removing the unwanted greater elements gives same, {4, 3, 3, 4}, and in this case if we apply maximum sum without adjacent elements on {4, 3, 3, 4} we will get 4+3=7 as answer but in real all of 4 3 3 4 are neagtion(-ve)
basically find a subarray following condition like 3 6 5 6 4 and break where u stop getting that property… first check if alternate elements are smaller than their neighbours and also check sum of 3+5>=6 … 5+4>=6 and so on… and apply that algo to only that part…
in the example u gave… all 4,3,3,4 will be handled differently… so all will be taken negative… so that algo will be use 4 times… one for 4 and then loop breaks… again for 3… and so on
@l_returns i checked ur code and in dp part i am confused can u tell in which part of that code u handeled we have to take adjacent like in this {4 5 3 5 3 5 4} and in which we dont have to like in this {4 10 3 10 3 10 4}
@abhi55, 4 10 3 10 3 10 4 cannot be called as “bad” because every 10 > sum of its adjacent terms 10 > 4 + 3, 10 > 3 + 3, 10 > 3 + 4. This is a example of the “good” set. The correct answer would be to make all 3s and 4s in this example negative (therefore including their indices).
I did this preproc. in the input string. Find all ranges of “good”, “bad” and “good/bad” sets. if input is
1 5 1 1 4 5 3 5 3 4 4 3 5 1 4 3
for this input, good - {1, 5, 1}, bad - {4, 5, 3, 5, 3, 4}, and good/bad - {3, 5, 1, 4, 3} ).
-Every possible element in “good” set should be inverted.
-Use above algo for “bad”
-Divide every good/bad set into good and bad (recursively?) to simplify them as good or bad
As @l_returns suggests, DP is possible and quite intuitive to solve this problem. However I was getting TLE in JAVA for this approach so had to look for a faster way