function LSS(list) {
const len = list.length;
let max = -Number.MAX_VALUE;
let sum = 0;
for (let i = 0; i < len; i++) {
sum = 0;
for (let j = i; j < len; j++) {
sum += list[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}
Java:
class MaximumSubarrayPrefixSum {
public int maxSubArray(int[] nums) {
int len = nums.length;
int maxSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < len; i++) {
sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}
}
Python 3:
import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
maxSum = -sys.maxsize
sum = 0
for i in range(n):
sum = 0
for j in range(i, n):
sum += nums[j]
maxSum = max(maxSum, sum)
return maxSum
function helper(list, m, n) {
if (m === n) return list[m];
let sum = 0;
let lmax = -Number.MAX_VALUE;
let rmax = -Number.MAX_VALUE;
const mid = ((n - m) >> 1) + m;
const l = helper(list, m, mid);
const r = helper(list, mid + 1, n);
for (let i = mid; i >= m; i--) {
sum += list[i];
if (sum > lmax) lmax = sum;
}
sum = 0;
for (let i = mid + 1; i <= n; i++) {
sum += list[i];
if (sum > rmax) rmax = sum;
}
return Math.max(l, r, lmax + rmax);
}
function LSS(list) {
return helper(list, 0, list.length - 1);
}
Java:
class MaximumSubarrayDivideConquer {
public int maxSubArrayDividConquer(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return helper(nums, 0, nums.length - 1);
}
private int helper(int[] nums, int l, int r) {
if (l > r) return Integer.MIN_VALUE;
int mid = (l + r) >>> 1;
int left = helper(nums, l, mid - 1);
int right = helper(nums, mid + 1, r);
int leftMaxSum = 0;
int sum = 0;
// left surfix maxSum start from index mid - 1 to l
for (int i = mid - 1; i >= l; i--) {
sum += nums[i];
leftMaxSum = Math.max(leftMaxSum, sum);
}
int rightMaxSum = 0;
sum = 0;
// right prefix maxSum start from index mid + 1 to r
for (int i = mid + 1; i <= r; i++) {
sum += nums[i];
rightMaxSum = Math.max(sum, rightMaxSum);
}
// max(left, right, crossSum)
return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));
}
}
Python 3 :
import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums) - 1)
def helper(self, nums, l, r):
if l > r:
return -sys.maxsize
mid = (l + r) // 2
left = self.helper(nums, l, mid - 1)
right = self.helper(nums, mid + 1, r)
left_suffix_max_sum = right_prefix_max_sum = 0
sum = 0
for i in reversed(range(l, mid)):
sum += nums[i]
left_suffix_max_sum = max(left_suffix_max_sum, sum)
sum = 0
for i in range(mid + 1, r + 1):
sum += nums[i]
right_prefix_max_sum = max(right_prefix_max_sum, sum)
cross_max_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid]
return max(cross_max_sum, left, right)
解法三 - 动态规划
思路
我们来思考一下这个问题, 看能不能将其拆解为规模更小的同样问题,并且能找出 递推关系。
我们不妨假设问题 Q(list, i) 表示 list 中以索引 i 结尾的情况下最大子序列和, 那么原问题就转化为 Q(list, i), 其中 i = 0,1,2...n-1 中的最大值。
我们继续来看下递归关系,即 Q(list, i)和 Q(list, i - 1)的关系, 即如何根据 Q(list, i - 1) 推导出 Q(list, i)。
如果已知 Q(list, i - 1), 我们可以将问题分为两种情况,即以索引为 i 的元素终止, 或者只有一个索引为 i 的元素。
如果以索引为 i 的元素终止, 那么就是 Q(list, i - 1) + list[i]
如果只有一个索引为 i 的元素,那么就是 list[i]
分析到这里,递推关系就很明朗了,即Q(list, i) = Math.max(0, Q(list, i - 1)) + list[i]
举例说明,如下图:
这种算法的时间复杂度 O(N), 空间复杂度为 O(1)
代码
JavaScript:
function LSS(list) {
const len = list.length;
let max = list[0];
for (let i = 1; i < len; i++) {
list[i] = Math.max(0, list[i - 1]) + list[i];
if (list[i] > max) max = list[i];
}
return max;
}
Java:
class MaximumSubarrayDP {
public int maxSubArray(int[] nums) {
int currMaxSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currMaxSum = Math.max(currMaxSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, currMaxSum);
}
return maxSum;
}
}
Python 3:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
max_sum_ending_curr_index = max_sum = nums[0]
for i in range(1, n):
max_sum_ending_curr_index = max(max_sum_ending_curr_index + nums[i], nums[i])
max_sum = max(max_sum_ending_curr_index, max_sum)
return max_sum
解法四 - 数学分析
思路
我们来通过数学分析来看一下这个题目。
我们定义函数 S(i) ,它的功能是计算以 0(包括 0)开始加到 i(包括 i)的值。
那么 S(j) - S(i - 1) 就等于 从 i 开始(包括 i)加到 j(包括 j)的值。
我们进一步分析,实际上我们只需要遍历一次计算出所有的 S(i), 其中 i 等于 0,1,2....,n-1。 然后我们再减去之前的 S(k),其中 k 等于 0,1,i - 1,中的最小值即可。 因此我们需要 用一个变量来维护这个最小值,还需要一个变量维护最大值。
这种算法的时间复杂度 O(N), 空间复杂度为 O(1)。
其实很多题目,都有这样的思想, 比如之前的《每日一题 - 电梯问题》。
代码
JavaScript:
function LSS(list) {
const len = list.length;
let max = list[0];
let min = 0;
let sum = 0;
for (let i = 0; i < len; i++) {
sum += list[i];
if (sum - min > max) max = sum - min;
if (sum < min) {
min = sum;
}
}
return max;
}
Java:
class MaxSumSubarray {
public int maxSubArray3(int[] nums) {
int maxSum = nums[0];
int sum = 0;
int minSum = 0;
for (int num : nums) {
// prefix Sum
sum += num;
// update maxSum
maxSum = Math.max(maxSum, sum - minSum);
// update minSum
minSum = Math.min(minSum, sum);
}
return maxSum;
}
}
Python 3:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
maxSum = nums[0]
minSum = sum = 0
for i in range(n):
sum += nums[i]
maxSum = max(maxSum, sum - minSum)
minSum = min(minSum, sum)
return maxSum