- 浏览: 19241 次
- 性别:
- 来自: 北京
文章分类
最新评论
题目描述
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.
解题思路
本问题是一个最大子串和问题,利用Kadane算法解决,时间复杂度为O(n)。但是在解决本题时需要注意Kadane算法只能解决有正数时的问题,因此还需要考虑全是负数的场景。具体Kadane算法思路见http://blog.csdn.net/joylnwang/article/details/6859677。
源代码
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.
解题思路
本问题是一个最大子串和问题,利用Kadane算法解决,时间复杂度为O(n)。但是在解决本题时需要注意Kadane算法只能解决有正数时的问题,因此还需要考虑全是负数的场景。具体Kadane算法思路见http://blog.csdn.net/joylnwang/article/details/6859677。
源代码
package leetcode; public class MaximumSubarray { public int maxSubArray1(int[] A) {//此方法超时,不适用 int length = A.length; int sum = A[0]; for(int i = 0; i < length; i++){ int temp = A[i]; if(temp > sum) sum = temp; for(int j = i + 1; j < length; j++){ temp += A[j]; if(temp > sum) sum = temp; } } return sum; } public int maxSubArray(int[] A){ //判断是否全是负数,如果不是全为负数,则可以使用Kadane算法 boolean allNegative = true; for(int i = 0; i < A.length; i++){ if(A[i] > 0) {allNegative = false;break;} } if(allNegative){ int returns = A[0]; for(int i = 0; i < A.length; i++){ if(A[i] > returns) returns = A[i]; } return returns; } //Kadane算法 int left, right, curLeft, curRigth, max, curMax; left = 0; right = 0; curLeft = 0; curRigth = 0; max = A[0]; curMax = 0; for(int i = 0; i < A.length; i++){ curMax += A[i]; if(curMax > 0){ curRigth = i; if(curMax > max){ max = curMax; left = curLeft; right = curRigth; } } else{ curMax = 0; left = i + 1; right = i + 1; } } return max; } public static void main(String[] args) { //int[] A = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int[] A = {-2, -1}; MaximumSubarray ms = new MaximumSubarray(); System.out.println(ms.maxSubArray(A)); } }
发表评论
-
Java中String与StringBuffer的区别
2014-10-29 21:07 301String和StringBuffer的区别,网上资料可以说 ... -
String to Integer (atoi)
2014-10-29 17:13 400题目描述 Implement atoi to convert ... -
Implement strStr()
2014-10-28 15:17 287题目描述 Implement strStr(). Retu ... -
Valid Palindrome
2014-10-23 10:32 423题目描述 Given a string, determine ... -
ZigZag Conversion
2014-10-22 19:51 342题目描述 The string "PAYPALIS ... -
Add Binary
2014-10-22 19:43 303题目描述 Given two binary strings, ... -
Longest Common Prefix
2014-10-22 19:44 332题目描述 Write a function to find t ... -
Count and Say
2014-10-22 19:44 347题目描述 The count-and-say sequence ... -
Valid Sudoku
2014-10-21 10:22 357题目描述 Determine if a Sudoku is v ... -
Valid Parentheses
2014-10-21 09:41 327题目描述 Given a string containing ... -
Palindrome Number
2014-10-21 09:41 348题目描述 Determine whether an integ ... -
Length of Last Word
2014-10-21 09:41 358题目描述 Given a string s consists ... -
Minimum Depth of Binary Tree
2014-10-21 09:41 310题目描述 Given a binary tree, find ... -
Remove Nth Node From End of List
2014-10-20 16:36 259题目描述 Given a linked list, remov ... -
Path Sum
2014-10-20 15:37 298题目描述 Given a binary tree and a ... -
Binary Tree Level Order Traversal II
2014-10-20 11:17 236题目描述 Given a binary tree, retur ... -
Binary Tree Level Order Traversal
2014-10-20 11:03 293题目描述 Given a binary tree, retur ... -
Pascal's Triangle II
2014-10-20 10:07 259题目描述 Given an index k, return t ... -
Pascal's Triangle
2014-10-19 12:24 321题目描述 Given numRows, generate th ... -
Plus One
2014-10-19 11:51 340题目描述 Given a non-negative numbe ...
相关推荐
最大子数组总和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...