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 { // dp[i] = max(A[i], dp[i - 1] + A[i]) public int maxSubArray(int[] A) { if (A == null || A.length == 0) return 0; int[] dp = new int[A.length]; dp[0] = A[0]; int max = dp[0]; for (int i = 1; i < A.length; i++) { dp[i] = Math.max(A[i], A[i] + dp[i - 1]); if (dp[i] > max) max = dp[i]; } return max; } }
相关推荐
leetcode双人赛 leetcode-solution 闲暇之余,刷一下题,弥补数据结构和算法的短板 ...maximum-subarray 加一 plus-one 合并两个有序数组 merge-sorted-array 杨辉三角 pascals-triangle 杨辉三角 II pa
leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions ...Subarray Easy 动态规划 0069 Sqrt(x) Easy 二分、牛顿迭代 0070 Climbing Stairs Easy 动态规划 0075 Sort Colors M
easy_Maximum-Subarray 提交链接 / Submit (You need register/login first before submit.) (在提交前你需要先注册或登录) 题目描述 / Description Given an integer array nums, find the contiguous subarray ...
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...
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]
leetcode 编码练习 该存储库基于在添加 leetcode 问题的解决方案时自动化样板代码。 使用单个命令,可以获取问题信息,生成python可执行模板,生成测试文件,并在README末尾更新表。 此存储库用于获取问题信息。 ...
技巧积累异或的性质: 如果a ^ b = c,则a ^ c = b求最大/最小异或值,可以考虑Trie classic problem: leetcode-421.... Maximum Subarray leetcode-992. Subarrays with K Different Integers单调双端加速度-单队列技
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 和 oj LeetCode 解决方案 Java 版 Leetcode 问题分类 细绳 8 字符串到整数 ...oj_152_maximum_product_subarray / SRC /溶液/ oj_236_lowest_common_ancestor_of_bt / notes.md SRC /溶液/ oj
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 ...LeetCode ...LeetCode ...Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
动态规划——最大连续子序列和一维最大连续子序列和[x] LeetCode 53 Maximum Subarray设$d[i]$表示以序列中$s[i]$结尾的最大
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也...Subarray Easy #66 Plus One Easy #70 Climbing Stairs Easy #83 Remove Duplicates from Sorted L
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-...
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...
最大子序和](./Array/maximum-subarray.md) [0041 缺失的第一个整数](./Array/first-missing-positive.md) [0042 接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023...
leetcode 分类 LeetCode 152/152 ToDoList -1。 delete ...Subarray 是一个东西么? 18.汉诺塔 排序堆的建立..... 推排序 相当于优先队列 19.图的算法 kruskal prim dijstria flordy 似乎都拼错了。
java lru leetcode Learn-algorithms :laptop: Java实现的各种算法题解,主要有: : 剑指Offer题集 题目数量:197,详情分类: ...Subarray](./leetcode/动态规划-Maximum Length of Repeated Subar
对于每一道算法题会总结代码、时间复杂度以及一些好的blog排序(sort)数组(...Maximum SubarrayLeetCode 152 Maximum Product SubarrayLintCode 138 Subarray SumLintCode 139 Subarray Sum ClosestLeetCode 392 Is ...