Maximum Subarray
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
.
click to show more practice.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
这是个很经典的题目了。
两个方法:
1 动态规划法
2 二分法
这里是使用简单的动态规划法,只需要一个额外空间记录就可以了,只要知道方法,实现起来比二分法简单多了。
class Solution {
public:
int maxSubArray(int A[], int n) {
int tempSum = 0;
int maxSum = INT_MIN;
for (int i = 0; i < n; i++)
{
tempSum += A[i];
maxSum = max(tempSum, maxSum);
if (tempSum < 0) tempSum = 0;
}
return maxSum;
}
};
二分法关键: 当最大子序列出现在中间的时候,应该如何计算最大值?
1 要循环完左边和右边的序列
2 从中间到左边,找到最大值
3 从中间到右边,找到最大值
这个判断条件还是有点难想的。
不过本题卡我时间最长的居然是一个小问题:最左边的下标写成了0.狂晕!
class Solution {
public:
int maxSubArray(int A[], int n) {
if (n < 1) return 0;
if (n == 1) return A[0];
return biSubArray(A, 0, n-1);
}
//low和up均为C++存储内容的下标
int biSubArray(int A[], int low, int up)
{
if (low > up) return INT_MIN;
if (low == up) return A[low];
int mid = low+((up-low)>>1);
//low不小心写成了0,结果浪费了很长时间debug
int lSum = biSubArray(A, low, mid);
int rSum = biSubArray(A, mid+1, up);
int midLSum = INT_MIN;
int tempSum = 0;
//low不小心写成了0,结果浪费了很多时间调试。
for (int i = mid; i >= low; i--)
{
tempSum += A[i];
//注意:条件的构造
if (tempSum > midLSum)
midLSum = tempSum;
}
int midRSum = INT_MIN;
tempSum = 0;
for (int i = mid+1; i <= up; i++)
{
tempSum += A[i];
if (tempSum > midRSum)
midRSum = tempSum;
}
int midSum = midLSum + midRSum;
return max(max(lSum,rSum), midSum);
}
};
分享到:
相关推荐
easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the contiguous subarray ...
技巧积累异或的性质: 如果a ^ b = c,则a ^ c = b求最大/最小异或值,可以考虑Trie classic problem: leetcode-421.... Maximum Subarray leetcode-992. Subarrays with K Different Integers单调双端加速度-单队列技
动态规划——最大连续子序列和一维最大连续子序列和[x] LeetCode 53 Maximum Subarray设$d[i]$表示以序列中$s[i]$结尾的最大
318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...
活动选择(Activity Selection) 备选列表排列(Alternative List Arrange) Davis–Putnam–Logemann–Loveland算法 ...最大子数组(Maximum Subarray) 最大子序列(Maximum Subsequence) 嵌套括号(Nested Brackets
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions ...Subarray Easy 动态规划 0069 Sqrt(x) Easy 二分、牛顿迭代 0070 Climbing Stairs Easy 动态规划 0075 Sort Colors M
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也...Subarray Easy #66 Plus One Easy #70 Climbing Stairs Easy #83 Remove Duplicates from Sorted L
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 ...LeetCode ...LeetCode ...Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: ...#53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先队列 #23:Merge k Sorted Lists
Maximum Subarray Minimum Path Sum Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle...
Maximum Subarray [53]5. House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. Palindromic Substrings [647]9. Maximum Length of Pair Chain [646]10. Integer Break [343]11. ...
leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...
leetcode 分类 LeetCode 152/152 ToDoList -1。 delete ...Subarray 是一个东西么? 18.汉诺塔 排序堆的建立..... 推排序 相当于优先队列 19.图的算法 kruskal prim dijstria flordy 似乎都拼错了。
53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock III 141.Linked List Cycle 142.Linked List Cycle II...
Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机 Best Time to Buy and Sell Stock 122 买卖股票的最佳时机 Ⅱ Best Time to Buy and Sell StockⅡ 123 买卖股票的最佳时机 Ⅲ Best Time to Buy...
Subarray] [70. Climbing Stairs] [101. Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is sorted] Medium [2. Add Two Numbers]
对于每一道算法题会总结代码、时间复杂度以及一些好的blog排序(sort)数组(...Maximum SubarrayLeetCode 152 Maximum Product SubarrayLintCode 138 Subarray SumLintCode 139 Subarray Sum ClosestLeetCode 392 Is ...
#Leetcode我的leetcode记录## 1。从有序数组中删除重复项public static int removeDuplicates( int [] nums) { int i = 0 ; for ( int n : nums) if (i == 0 ... Maximum Subarray问题描述:定义一个整体的副本,从中寻
加油站 ...Subarray325Maximum大小子阵总和脱节IntervalsTreeMapCounter239Sliding窗口Maximum295Find中位数的距离和很少考289Game的提高321Create最大数量很少考327Count的Equals k209Minimum大小的数组
lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ...