This approach uses Kadane's Algorithm, which is an efficient way to find the maximum subarray sum in linear time.
We iterate through the array, keeping track of the maximum sum of the subarray ending at the current position and the overall maximum sum found so far.
The algorithm maintains two variables: current_max, which is the maximum sum of the subarray that ends at the current index, and global_max, which is the maximum sum found so far.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), because we are using a constant amount of extra space.
1public class MaxSubArray {
2 public int maxSubArray(int[] nums) {
3 int currentMax = nums[0];
4 int globalMax = nums[0];
5
6 for (int i = 1; i < nums.length; i++) {
7 currentMax = Math.max(nums[i], currentMax + nums[i]);
8 if (currentMax > globalMax) {
9 globalMax = currentMax;
10 }
11 }
12
13 return globalMax;
14 }
15
16 public static void main(String[] args) {
17 MaxSubArray solution = new MaxSubArray();
18 int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
19 System.out.println("Maximum subarray sum is " + solution.maxSubArray(nums));
20 }
21}This Java code implements Kadane's Algorithm, updating currentMax and globalMax during the iteration.
This approach splits the array into two halves and finds the maximum subarray sum for each half recursively. It also considers the possibility of the maximum subarray crossing the midpoint.
To find the maximum crossing subarray, we begin at the midpoint and expand outward to the left and right, keeping track of the maximum sum.
This approach effectively divides the problem into smaller subproblems and conquers each independently, then combines their results.
Time Complexity: O(n log n)
Space Complexity: O(log n) for the recursion stack
1def max_crossing_sum(arr, left, mid, right):
2 left_sum = float('-inf')
3 total = 0
4 for i in range(mid, left - 1, -1):
5 total += arr[i]
6 if total > left_sum:
7 left_sum = total
8
9 right_sum = float('-inf')
10 total = 0
11 for i in range(mid + 1, right + 1):
12 total += arr[i]
13 if total > right_sum:
14 right_sum = total
15
16 return left_sum + right_sum
17
18def max_sub_array_sum(arr, left, right):
19 if left == right:
20 return arr[left]
21
22 mid = (left + right) // 2
23
24 left_max = max_sub_array_sum(arr, left, mid)
25 right_max = max_sub_array_sum(arr, mid + 1, right)
26 crossing_max = max_crossing_sum(arr, left, mid, right)
27
28 return max(left_max, right_max, crossing_max)
29
30# Example usage
31nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
32print("Maximum subarray sum is", max_sub_array_sum(nums, 0, len(nums) - 1))This Python code uses a divide and conquer strategy, recursively calculating maximum subarray sums for the left, right, and crossing sections of the array. It combines these results to find the overall maximum subarray sum.