0 like 0 dislike
Example array : {0,1,1,1,-5,2,-4} .

Answer = {1,1,-5,2,-4}  is the largest subarray whose sum is odd.

Rules :

1)Explanation of algorithm in your answer is a must .

2)Writing code is optional .

3)If code is written , make sure to you use format option from the editor .
in Algorithms and Problems by Expert (17,730 points) | 234 views

1 Answer

1 like 0 dislike
  1. Calculate prefix sum and store it in a new array.
  2. A. If the last element is odd, then return the array.

           B. If not, then

                   I. Find out the last odd sum in prefix array and take the length from first to last odd sum.

                   II.  Find out the first odd sum in the prefix array and then take the length of the array from the first odd sum to the last element.

       3. Return the array with a maximum length

by Expert (610 points)