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

**Problem Note**

- A contiguous subarray of an array A[ ] of length n is a contiguous segment from A[i] through A[j] where
**0<= i <= j <= n.** - Array A[ ] 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: A[] = [-5, 8, 9, -6, 10, -15, 3]
Output: 21
Explanation: The subarray [8, 9, -6, 10] has the maximum sum.
```

**Example 2 **

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

**Example 3 **

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