Problem of the day
You are given an array 'arr' of length 'n', consisting of integers.
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].
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
Using basic implementation, let’s check for all subarrays to find the maximum sum among them.
Let us check for all possible subarrays of the array. For this, we run two loops, where the outer loop points to the left boundary and the inner loop points to the outer boundary of the subarray.
Using another loop inside, find the sum of this subarray. Compare it with the maximum subarray sum obtained so far. After checking all the subarrays, simply return the maximum sum found.
O(n ^ 3), where ‘n’ is the length of the array.
There are n * (n + 1) / 2 subarrays in total, and for each subarray, we find its sum in O(n) time.
O(1), as constant extra space is required.