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
.
public class Solution { public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int max = Integer.MIN_VALUE; int cur = 0; for (int i = 0; i < nums.length; i++) { cur += nums[i]; max = Math.max(max, cur); if (cur < 0) { cur = 0; } } return max; } }
相关推荐
最大子数组总和maximum subarray sum使用Java语言中的所有复杂度来计算子数组的最大和。 1.O(n ^ 3) 2.O(n ^ 2) 3.O(n)
活动选择(Activity Selection) 备选列表排列(Alternative List Arrange) Davis–Putnam–Logemann–Loveland算法 ...最大子数组(Maximum Subarray) 最大子序列(Maximum Subsequence) 嵌套括号(Nested Brackets
Maximum subarray problem Bit-Set Queue Stack Binary Heap Fibonacci Heap Priority Queue (list based) Bubble sort Selection sort Insertion sort Radix sort Quick sort Merge sort Heap sort Double linked...
最大子序列和问题(Maximum Subarray Sum Problem)是求解一个数组中连续子数组的和的最大值的问题。
easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the contiguous subarray ...
Maximum Product Subarray Longest Increasing Subsequence Palindrome Partitioning II Maximal Rectangle Best Time to Buy and Sell Stock III Best Time to Buy and Sell Stock IV Best Time to Buy and Sell ...
动态规划——最大连续子序列和一维最大连续子序列和[x] LeetCode 53 Maximum Subarray设$d[i]$表示以序列中$s[i]$结尾的最大
Maximum XOR With an Element From ArraysubSequence问题一般可以用DP解决,复杂度为O(N ^ 2) subArray问题一般可以使用滑动窗口方法(或以DP结尾,在这种情况下本质也是一种滑动窗口方法),复杂度O(N) ...
2.4 Maximum subarray sum . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Sorting 25 3.1 Sorting theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Sorting in C++ . . ...
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: ...#53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先队列 #23:Merge k Sorted Lists
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions ...Subarray Easy 动态规划 0069 Sqrt(x) Easy 二分、牛顿迭代 0070 Climbing Stairs Easy 动态规划 0075 Sort Colors M
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. ...
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...
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 ...Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ANAGRAMS 7 COUNTING ELEMENTS 日 问题描述 问题和解决方案链接 Git 解决方案页面 8 Middle of the Linked List 9 Backspace String ...
加油站 ...Subarray325Maximum大小子阵总和脱节IntervalsTreeMapCounter239Sliding窗口Maximum295Find中位数的距离和很少考289Game的提高321Create最大数量很少考327Count的Equals k209Minimum大小的数组
加油站 leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167....2107/03/06 15.3 ...Subarray, 91.Decode Ways, 96.Unique Binary Search Tree, 120.Triangle, 139.Word Break, 152.Maximum Produ
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也...Subarray Easy #66 Plus One Easy #70 Climbing Stairs Easy #83 Remove Duplicates from Sorted L
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...