Maximum Subarray Sum

Problem:
Given an integer array A, find the contiguous subarray (containing at least one number) which has the largest sum.

Example:
A = [-2,1,-3,4,-1,2,1,-5,4], The largest sum should be 6, we choose [4,-1,2,1] subarray.

Approach:
There are few approaches to solve this problem.
We are going to solve it by Kadane's Algorithm, and Prefix Sum.

In Kadanes Algorithm we will do three operations:

1.  Add Current elements of the array to a variable named Sum.
2. Update Largest Sum with Sum.
3. If the current Sum is negative make it Zero.

This is the code of Maximum Subaarray sum using the Kadanes Algorithm. Simply we traverse the whole array by doing three operations.

In Prefix Sum Approach we usually do two types of operations, Before calculating the largest subarray sum, we have to build a prefix array.

By traversing every element of prefix array, 

1. Every time we remove a minimum prefix value from the current prefix value by comparing the largest sum.

2. Update minimum value