Maximum Subarray
maximum Subarray
2023-09-11 14:20:12 时间
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4]
,
the contiguous subarray [4,−1,2,1]
has the largest sum = 6
.
求最大连续子序列和。
若到 i 之前的连续序列的和为正,那么 i 就接受这个和,若为负,i 就丢弃掉,从自身开始累加(就是将原来累加的和清零),然后判断当前的累积是不是不是比最大结果大,若是,则更新最大结果为当前累积和。
class Solution { public: int maxSubArray(int A[], int n) { int max = -0x7f7f7f7f; int sum = 0; for(int i = 0; i < n; ++i) { if(sum < 0) sum = 0; sum += A[i]; if(sum > max) max = sum; } return max; } };
相关文章
- Lintcode: Maximum Subarray III
- Lintcode: Maximum Subarray II
- Leetcode: Maximum Subarray
- 非极大值抑制(Non-Maximum Suppression,NMS)
- POJ 3693 Maximum repetition substring (后缀数组+RMQ)
- 【LeetCode】53. Maximum Subarray (2 solutions)
- 由Maximum Gap,对话桶排序,基数排序和统计排序
- [LeetCode] 1239. Maximum Length of a Concatenated String with Unique Characters 串联字符串的最大长度
- [LeetCode] 1072. Flip Columns For Maximum Number of Equal Rows 按列翻转得到最大值等行数
- [LeetCode] 895. Maximum Frequency Stack 最大频率栈
- 718. Maximum Length of Repeated Subarray