Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You are given an array * 'arr'* of length

A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.

Find the sum of the subarray **(including empty subarray)** having maximum sum among all subarrays.

The sum of an empty subarray is 0.

```
Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]
Output: 11
Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].
```

Detailed explanation

```
The first line of input contains an integer 'n', representing the array's length.
The second line of input contains 'n' single space-separated integers, denoting the elements of the array.
```

```
The output contains the maximum subarray sum.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
9
1 2 7 -4 3 2 -10 9 1
```

```
11
```

```
The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].
```

```
6
10 20 -30 40 -50 60
```

```
60
```

```
3
-3 -5 -6
```

```
0
```

```
The expected time complexity is O(n).
```

```
1 <= 'n' <= 10 ^ 6
-10 ^ 6 <= 'arr[i]' <= 10 ^ 6
Time limit: 1sec
```