Problem
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
ExampleFor 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.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Solutionclass Solution { public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) return 0; int max = nums[0], sum = max; for (int i = 1; i < nums.length; i++) { if (sum < 0) { sum = nums[i]; } else { sum += nums[i]; } max = Math.max(max, sum); } return max; } }
class Solution { public int maxSubArray(int[] nums) { int sum = nums[0], n = nums.length; int[] dp = new int[n]; dp[0] = sum; for (int i = 1; i < n; i++) { if (sum < 0) sum = nums[i]; else sum += nums[i]; dp[i] = Math.max(dp[i-1], sum); } return dp[n-1]; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/68243.html
摘要:复杂度思路要保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现,所以到这一位为止的能得到的最大值,可能是由之前的最大值和这个数相乘得到,也可能是最小值和这个数相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...
Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...
摘要:最新更新请见原题链接动态规划复杂度时间空间思路这是一道非常典型的动态规划题,为了求整个字符串最大的子序列和,我们将先求较小的字符串的最大子序列和。而最大子序列和的算法和上个解法还是一样的。 Maximum Subarray 最新更新请见:https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...
摘要:题目详情输入一个数组和一个整数。要求找出输入数组中长度为的子数组,并且要求子数组元素的加和平均值最大。 题目详情 Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need ...
摘要:题目要求从一个整数数组中找到一个子数组,该子数组中的所有元素的乘积最大。比如数组的最大乘积子数组为思路与代码这题目考察了动态编程的思想。至于为什么还要比较,是因为如果是一个负数的,那么之前的最小乘积在这里可能就成为了最大的乘积了。 题目要求 Find the contiguous subarray within an array (containing at least one num...
摘要:这是一道简单的动规题目,同步更新数组解决了为负数的问题。即使是求最小乘积子序列,也可以通过取和的最小值获得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...
阅读 3153·2023-04-26 03:06
阅读 3665·2021-11-22 09:34
阅读 1112·2021-10-08 10:05
阅读 2996·2021-09-22 15:53
阅读 3425·2021-09-14 18:05
阅读 1286·2021-08-05 09:56
阅读 1744·2019-08-30 15:56
阅读 2096·2019-08-29 11:02