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
1function maxCrossingSum(arr, l, m, h) {
2 let leftSum = -Infinity;
3 let sum = 0;
4 for (let i = m; i >= l; i--) {
5 sum += arr[i];
6 if (sum > leftSum)
7 leftSum = sum;
8 }
9
10 let rightSum = -Infinity;
11 sum = 0;
12 for (let i = m + 1; i <= h; i++) {
13 sum += arr[i];
14 if (sum > rightSum)
15 rightSum = sum;
16 }
17
18 return leftSum + rightSum;
19}
20
21function maxSubArraySum(arr, l, h) {
22 if (l === h) {
23 return arr[l];
24 }
25
26 const mid = Math.floor((l + h) / 2);
27
28 const leftMax = maxSubArraySum(arr, l, mid);
29 const rightMax = maxSubArraySum(arr, mid + 1, h);
30 const crossMax = maxCrossingSum(arr, l, mid, h);
31
32 return Math.max(leftMax, rightMax, crossMax);
33}
34
35// Example usage
36const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
37console.log("Maximum subarray sum is", maxSubArraySum(nums, 0, nums.length - 1));This JavaScript solution employs the divide and conquer method. By recursively calculating the maximum for different sections of the array, it seeks an optimal subarray sum while evaluating crossing parts.