新博文地址:[leetcode]Maximum Subarray
http://oj.leetcode.com/problems/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.
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.
很经典的DP问题,不多说,一个需要注意的地方:
当全部为负数时,只能去最小的负数,而不是返回0。复杂度O(n)。
分治法:复杂度O(n^2)。见新博文。
public int maxSubArray(int[] A) { if(A == null || A.length == 0){ return 0; } int max = Integer.MIN_VALUE; int sum = 0; for (int i = 0; i < A.length; i++) { if (sum <= 0){ sum = 0; } sum += A[i]; if (sum > max){ max = sum; } } return max; }
相关推荐
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 ...