Given an array of integers consisting of both positive and negative

numbers, find the contiguous subsequence that has the**maximum sum** among all subsequences in the array (click the red text to learn more about subsequences). Write a method that takes in

an array of integers

Examples:

numbers, find the contiguous subsequence that has the

an array of integers

`arr`

and returns an array `res`

containing 3 integers in the following format:

res[0] = max sum

res[1] = starting index of the subsequence

res[2] = ending index of the subsequence

Examples:

`maxContSequence({-1,-2,3,4,5}) ==> {12,2,4}`

`maxContSequence({1,2,3,-2,5}) ==> {6,0,2}`

Need a **hand?** Try out these hints, one at a time.

Use 4 temporary variables : one to store the maximum possible sum, one to store the current sum and the other two to keep track of the starting and ending indices of the sequence whose elements contribute to the maximum sum. Iterate over the array and use these variables for book keeping.

1. Initialize the variables to keep a track of the

2. Loop over the array. Add the current element to the current temporay sum and do the following comparisions :

3. If the

4. Else include the current element into the

5. If

`max_sum`

, representing the global maximum sum, `curr_sum`

representing the current temporary sum, `start index`

and the `end index`

of the array's elements representing the start and end indices of the contiguous subsequence whose sum will be maximum. 2. Loop over the array. Add the current element to the current temporay sum and do the following comparisions :

3. If the

`current sum`

is less than the value of the current element, make the current element the `current sum`

. The index of the current element becomes the start and end indices of the subsequence.4. Else include the current element into the

`current sum`

and set the index of the current element as the ending index of the subsequence.5. If

`current sum`

is greater than `max sum`

update the `max sum`

with the `current sum`

and store the start index and end index in temporary variables which will be returned back along with the sum in the `res`

array.
public static int[] maxContSequence(int[] arr) { }

**C**

**Java**

**Python**