class Main {
/*
Given an array of integers, both negative and non-negative,
find the contiguous subarray with the largest sum and
return the sum of that subarray.
input = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
output = 6
// initialize two variables --> maxSoFar and maxEndHere = 0
// Iterate through integers
// for each integer--> update both variables to be max of current integer or the sum of current integer
// update maxSoFar --> max of both variables
// continue update until iteration of all integers
// return the maxSoFar --> contain maximum sub array
*/
/*
Time Complexity: O(n) - Linear time complexity due to iterating through the input array once.
Space Complexity: O(1) - Constant space complexity as the function uses a fixed number of additional variables.
*/
public static int maxSubArray(int[] nums){
int maxSoFar = nums[0];
int maxEndHere = nums[0];
// iterate through integers
for(int i=1; i<nums.length; i++){ // iterate from 2ndt element,beacasue variables are asiigned at 1.
maxEndHere = Math.max(nums[i], maxEndHere + nums[i]); // (current element, sum of current element)
maxSoFar = Math.max(maxSoFar, maxEndHere); // max of current element or sum of current element
}
return maxSoFar;
}
public static void main(String[] args) {
int[] input = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int isMaxSumArray = maxSubArray(input);
System.out.println(isMaxSumArray);
}
}
