Given an integer array nums, find the subarray with the largest sum and return its sum.
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Subarray [4,-1,2,1] has the largest sum = 6.
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4The brute force checks every possible subarray's sum directly — O(n^2) if you track a running sum per starting index, O(n^3) if you resum from scratch each time.
At each position, you're really only ever asking one question: is it better to EXTEND the best subarray ending at the previous position, or to START FRESH here? That's Kadane's core insight.
A negative running sum can never help a future subarray — if currentSum drops below the value of the current element alone, discard it and restart from here.
public int maxSubArrayBruteForce(int[] nums) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}Time: O(n^2) · Space: O(1)