# Maximum Subarray Sum

Last updated: 17 Jan, 2021

#### Problem Statment

Given an integer array A of N elements. You need to find the maximum sum possible of its subarray.

Example 1:
Input
3
7
1 2 3 4 -10 9 4
5
1 2 3 4 5
7
5 4 -10 -5 1 5 6
Output:
13
15
12
Method:

Brute Force

One way to solve this problem is to get all the subarrays of the array and sum them individually and print the highest sum amount.

Let's look at an Optimised approach

The idea is to calculate,for each array position , the maximum sum of subarray at that position.

- Add each integer of the array to a variable "sum"
- Update sum with the max value between sum and array[i] + sum
- Keep an integer "best" which will store the max value of the sum

This method solves the problem in O(n)

###### Python Code

    test=int(input())
    for i in range(test):
        size=int(input())
        arr=list(map(int,input().split()))
        best=0
        sum=0
        for j in range(size):
            sum=max(arr[j],arr[j]+sum)
            best=max(sum,best)
        print(best)