You are given an array arr[] with n elements. Write a program to find the contiguous subarray which has the largest sum.

Problem Note

• A contiguous subarray of an array arr[] of length n is a contiguous segment from A[i] through A[j] where 0<= i <= j <= n.
• Array arr[] may contain both positive and negative integers. If the array contains all non-negative numbers, the maximum subarray is the entire array.

Example 1

Input: arr[] = [-5, 8, 9, -6, 10, -15, 3] 
Output: 21
Explanation: The subarray [8, 9, -6, 10] has the maximum sum.

Example 2

Input: arr[] = [-4, -7, -1, 5, -2] 
Output: 4 
Explanation: The subarray [-1, 5] has the maximum sum.

Example 3

Input: arr[] = [1, 6, 2, 4] 
Output: 13 
Explanation: All elements are non-negative numbers,the maximum subarray is the entire array.