Calculating the maximum non-contiguous subarray is pretty obvious, we simply take all the positive numbers and summarize them. Now for the contiguous part, for calculating it we can use a simple algorithm called "Kadaen Algorithms". I will try to describe it . We keep an integer which shows the best answer we got so far ( we will call it ANS) and one more integer which shows the current sum which we got by summing some elements. Now we begin summing the elements, at every step we update the ANS. and if at some point we got a current sum which is a negative number then there is no need to keep the elements which we summed so far, we would rather drop them and start picking new elements on the way. Check out the source code for a better understanding.
No comments:
Post a Comment