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.
1#include <stdio.h>
2#include <limits.h>
3
4int maxSubArray(int* nums, int numsSize) {
5 int current_max = nums[0];
6 int global_max = nums[0];
7
8 for (int i = 1; i < numsSize; i++) {
9 if (current_max < 0) {
10 current_max = nums[i];
11 } else {
12 current_max += nums[i];
13 }
14
15 if (current_max > global_max) {
16 global_max = current_max;
17 }
18 }
19
20 return global_max;
21}
22
23int main() {
24 int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
25 int size = sizeof(nums)/sizeof(nums[0]);
26 int max_sum = maxSubArray(nums, size);
27 printf("Maximum subarray sum is %d\n", max_sum);
28 return 0;
29}This C code implements Kadane's Algorithm. We initialize current_max and global_max to the first element of the array, then iterate through the array, updating these values based on the logic of Kadane's algorithm.
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.