Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
我的解法：两层循环 第一层循环通过i控制进度，第二层循环计算从i 开始的子数组的和的最大值
C#版解法：
public class Solution { public int MaxSubArray(int[] nums) { if(nums.Length == 0) return 0; int max = int.MinValue; for(int i = 0; i < nums.Length; i++){ int tempSum=0; for(int j =i; j < nums.Length; j++){ tempSum += nums[j]; if(tempSum > max) max = tempSum; } } return max; } }
看题目描述，可以使用divide and conquer（分而治之）思想去实现，时间复杂度会大幅度降低：这里先将解法贴出来，具体的分而治之（动态规划）的学习放到下一个文章中
static int maxCrossingSum(int[] arr, int l, int m, int h) { // Include elements on left of mid. int sum = 0; int left_sum = int.MinValue; for (int i = m; i >= l; i--) { sum = sum + arr[i]; if (sum > left_sum) left_sum = sum; } // Include elements on right of mid sum = 0; int right_sum = int.MinValue; ; for (int i = m + 1; i <= h; i++) { sum = sum + arr[i]; if (sum > right_sum) right_sum = sum; } // Return sum of elements on left // and right of mid return left_sum + right_sum; } // Returns sum of maxium sum subarray // in aa[l..h] static int maxSubArraySum(int[] arr, int l, int h) { // Base Case: Only one element if (l == h) return arr[l]; // Find middle point int m = (l + h) / 2; /* Return maximum of following three possible cases: a) Maximum subarray sum in left half b) Maximum subarray sum in right half c) Maximum subarray sum such that the subarray crosses the midpoint */ return Math.Max(Math.Max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m + 1, h)), maxCrossingSum(arr, l, m, h)); } /* Driver program to test maxSubArraySum */ public static void Main() { int[] arr = { -2, 3, 4, -5, 7 }; int n = arr.Length; int max_sum = maxSubArraySum(arr, 0, n - 1); Console.Write("Maximum contiguous sum is " + max_sum); Console.ReadKey(); }
分而治之的链接：算法学习 分而治之思想
LeetCode Array Easy 53. Maximum Subarray 个人解法 和分治思想的学习
原文：https://www.cnblogs.com/c-supreme/p/8893703.html