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.
1using System;
2
3public class MaxSubArray {
4 public int MaxSubArraySum(int[] nums) {
5 int currentMax = nums[0];
6 int globalMax = nums[0];
7
8 for (int i = 1; i < nums.Length; i++) {
9 currentMax = Math.Max(nums[i], currentMax + nums[i]);
10 if (currentMax > globalMax) {
11 globalMax = currentMax;
12 }
13 }
14
15 return globalMax;
16 }
17
18 public static void Main(string[] args) {
19 MaxSubArray solution = new MaxSubArray();
20 int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
21 Console.WriteLine("Maximum subarray sum is " + solution.MaxSubArraySum(nums));
22 }
23}This C# code implements Kadane's Algorithm, iterating through the array to find the maximum subarray sum. The Math.Max is utilized for calculating the maximum at each step.
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
1using System;
2
3public class MaxSubArrayDivideConquer {
4
5 public int MaxCrossingSum(int[] arr, int left, int mid, int right) {
6 int sum = 0;
7 int left_sum = Int32.MinValue;
8
9 for (int i = mid; i >= left; i--) {
10 sum += arr[i];
11 if (sum > left_sum)
12 left_sum = sum;
13 }
14
15 sum = 0;
16 int right_sum = Int32.MinValue;
17 for (int i = mid + 1; i <= right; i++) {
18 sum += arr[i];
19 if (sum > right_sum)
20 right_sum = sum;
21 }
22
23 return left_sum + right_sum;
24 }
25
26 public int MaxSubArraySum(int[] arr, int left, int right) {
27 if (left == right)
28 return arr[left];
29
30 int mid = (left + right) / 2;
31
32 int left_max = MaxSubArraySum(arr, left, mid);
33 int right_max = MaxSubArraySum(arr, mid + 1, right);
34 int cross_max = MaxCrossingSum(arr, left, mid, right);
35
36 return Math.Max(Math.Max(left_max, right_max), cross_max);
37 }
38
39 public static void Main(string[] args) {
40 MaxSubArrayDivideConquer solution = new MaxSubArrayDivideConquer();
41 int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
42 Console.WriteLine("Maximum subarray sum is " + solution.MaxSubArraySum(nums, 0, nums.Length - 1));
43 }
44}This C# code applies the divide and conquer method, determining the maximum subarray sum by recursive calls and considering the crossing middle elements.