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.
1function maxSubArray(nums) {
2 let currentMax = nums[0];
3 let globalMax = nums[0];
4
5 for (let i = 1; i < nums.length; i++) {
6 currentMax = Math.max(nums[i], currentMax + nums[i]);
7 if (currentMax > globalMax) {
8 globalMax = currentMax;
9 }
10 }
11
12 return globalMax;
13}
14
15// Example usage
16const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
17console.log("Maximum subarray sum is", maxSubArray(nums));This JavaScript code uses Kadane's Algorithm to determine the largest sum contiguous subarray. The Math.max function helps optimize the maximum subarray calculation.
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
1#include <iostream>
2#include <vector>
3#include <climits>
4
5using namespace std;
6
7int maxCrossingSum(vector<int>& nums, int l, int m, int h) {
8 int sum = 0;
9 int left_sum = INT_MIN;
10
11 for (int i = m; i >= l; i--) {
12 sum += nums[i];
13 if (sum > left_sum)
14 left_sum = sum;
15 }
16
17 sum = 0;
18 int right_sum = INT_MIN;
19
20 for (int i = m + 1; i <= h; i++) {
21 sum += nums[i];
22 if (sum > right_sum)
23 right_sum = sum;
24 }
25
26 return left_sum + right_sum;
27}
28
29int maxSubArraySum(vector<int>& nums, int l, int h) {
30 if (l == h)
31 return nums[l];
32
33 int m = (l + h) / 2;
34
35 int left_max = maxSubArraySum(nums, l, m);
36 int right_max = maxSubArraySum(nums, m + 1, h);
37 int cross_max = maxCrossingSum(nums, l, m, h);
38
39 return max(max(left_max, right_max), cross_max);
40}
41
42int main() {
43 vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
44 int max_sum = maxSubArraySum(nums, 0, nums.size() - 1);
45 cout << "Maximum subarray sum is " << max_sum << endl;
46 return 0;
47}This C++ solution uses the divide and conquer strategy to recursively find the maximum subarray sum. It calculates the maximum sum that crosses the midpoint of the array and combines the results from the left and right subarrays.