[LeetCode] Maximum Subarray Sum

简介: Dynamic Programming There is a nice introduction to the DP algorithm in this Wikipedia article. The idea is to maintain a running maximum smax and a current summation sum.

Dynamic Programming

There is a nice introduction to the DP algorithm in this Wikipedia article. The idea is to maintain a running maximum smax and a current summation sum. When we visit each num in nums, addnum to sum, then update smax if necessary or reset sum to 0 if it becomes negative.

The code is as follows.

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int sum = 0, smax = INT_MIN;
 5         for (int num : nums) {
 6             sum += num;
 7             if (sum > smax) smax = sum;
 8             if (sum < 0) sum = 0;
 9         }
10         return smax;
11     }
12 };

Divide and Conquer

The DC algorithm breaks nums into two halves and find the maximum subarray sum in them recursively. Well, the most tricky part is to handle the case that the maximum subarray may span the two halves. For this case, we use a linear algorithm: starting from the middle element and move to both ends (left and right ends), record the maximum sum we have seen. In this case, the maximum sum is finally equal to the middle element plus the maximum sum of moving leftwards and the maximum sum of moving rightwards.

Well, the code is just a translation of the above idea.

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int smax = INT_MIN, n = nums.size();
 5         return maxSub(nums, 0, n - 1, smax);
 6     }
 7 private:
 8     int maxSub(vector<int>& nums, int l, int r, int smax) {
 9         if (l > r) return INT_MIN;
10         int m = l + ((r - l) >> 1);
11         int lm = maxSub(nums, l, m - 1, smax); // left half
12         int rm = maxSub(nums, m + 1, r, smax); // right half
13         int i, sum, ml = 0, mr = 0;
14         // Move leftwards
15         for (i = m - 1, sum = 0; i >= l; i--) {
16             sum += nums[i];
17             ml = max(sum, ml); 
18         }
19         // Move rightwards
20         for (i = m + 1, sum = 0; i <= r; i++) {
21             sum += nums[i];
22             mr = max(sum, mr);
23         }
24         return max(smax, max(ml + mr + nums[m], max(lm, rm)));
25     }
26 };

 

目录
相关文章
Leetcode 53.Maximum Subarray
题意简单,给出一个数组,求出其中最大的子数组和。 这种简单题目背后蕴藏着很巧妙的解题方法。其实只需要遍历一次数组就可以求得解。 思路是这样的,你想想看,如果一段子数组的和是负数, 那么这一段子数组不可能是最大和数组的一部分,丢掉重新从下一个位置开始选。
50 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
97 0
LeetCode 414. Third Maximum Number
LeetCode 318. Maximum Product of Word Lengths
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
81 0
LeetCode 318. Maximum Product of Word Lengths
LeetCode 239. Sliding Window Maximum
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。 返回滑动窗口最大值。
64 0
LeetCode 239. Sliding Window Maximum
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String
LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String
LeetCode 104. 二叉树的最大深度 Maximum Depth of Binary Tree
LeetCode 104. 二叉树的最大深度 Maximum Depth of Binary Tree
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
63 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
125 2