PROBLEM DESCRIPTION
Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
long maxSubarraySum(int arr[], int n){
long maxSum = Long.MIN_VALUE;
long currentSum = 0;
for(int i=0; i<n; i++){
currentSum = Math.max(currentSum + arr[i], arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
}