arr[1...n]
You might ask what is a subarray?
SubArray is basically array within an array is called a sub array, as shown below 4, -1, 2 is the subarray of the given array arr[], So, a subarray is a set of contiguous elements in a given array.
Exxample :
Given an array of n elements
For example, for the array given above, the contiguous subarray with the largest sum is [4, -1, 2], with sum 5. We would use this array as our example. Also, we would assume this array to be zero-indexed, i.e. -2 would be called as the ‘0th’ element of the array and so on. Also, A[i] would represent the value at index i.
Kadane’s Algorithm:
From the example we see that the local maximum is [4] which on adding to the next element is 3 as the elements are [4, -1] , now when we move forward in the subarray we find the element [2] which sums up to give the result as 5. Therefore the maximum sum of the sub array is 5, So Kadane's Algorithm starts doing the sum with the max element found in the array because if the elements are in the negative order there is no need to carry the element forward, as we will see in the code below. Whenever the local_max element is found in the array it updates themax variable to keep track of the maximum sum subarray.
class maxSum{
public int maxSubArray(int[] arr) {
int sum = 0;
int max = arr[0];
for(int i = 0; i < arr.length; i++){
sum += arr[i];
if(sum > max) max = sum;
if(sum < 0) sum = 0;
}
return max;
}
}