[LeetCode] Maximum Subarray

Donald 發(fā)布于2019-08-15 13:40 / 1753人閱讀

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Example

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.

More practice

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

class 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;
    }
}

DP

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];
    }
}

云服務(wù)器 GPU云服務(wù)器 subarray Maximum LeetCode LeetCode_String

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/68243.html

相關(guān)文章

Leetcode[152] Maximum Product Subarray

摘要：復(fù)雜度思路要保留一個(gè)到某一位來(lái)看的最大值和最小值。因?yàn)樵跀?shù)組中有負(fù)數(shù)的出現(xiàn)，所以到這一位為止的能得到的最大值，可能是由之前的最大值和這個(gè)數(shù)相乘得到，也可能是最小值和這個(gè)數(shù)相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...

_ipo 2019-08-14 16:49 評(píng)論0 收藏0
[LeetCode] Maximum Size Subarray Sum Equals k

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 ...

MudOnTire 2019-08-15 15:47 評(píng)論0 收藏0
[Leetcode] Maximum Subarray 子序列最大和

摘要：最新更新請(qǐng)見(jiàn)原題鏈接動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路這是一道非常典型的動(dòng)態(tài)規(guī)劃題，為了求整個(gè)字符串最大的子序列和，我們將先求較小的字符串的最大子序列和。而最大子序列和的算法和上個(gè)解法還是一樣的。 Maximum Subarray 最新更新請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

summerpxy 2019-08-14 16:11 評(píng)論0 收藏0
leetcode 643 Maximum Average Subarray I

摘要：題目詳情輸入一個(gè)數(shù)組和一個(gè)整數(shù)。要求找出輸入數(shù)組中長(zhǎng)度為的子數(shù)組，并且要求子數(shù)組元素的加和平均值最大。題目詳情 Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need ...

SwordFly 2019-08-15 13:57 評(píng)論0 收藏0
leetcode152 Maximum Product Subarray

摘要：題目要求從一個(gè)整數(shù)數(shù)組中找到一個(gè)子數(shù)組，該子數(shù)組中的所有元素的乘積最大。比如數(shù)組的最大乘積子數(shù)組為思路與代碼這題目考察了動(dòng)態(tài)編程的思想。至于為什么還要比較，是因?yàn)槿绻且粋€(gè)負(fù)數(shù)的，那么之前的最小乘積在這里可能就成為了最大的乘積了。題目要求 Find the contiguous subarray within an array (containing at least one num...

Arno 2019-08-16 10:57 評(píng)論0 收藏0
[LintCode/LeetCode] Maximum Product Subarray

摘要：這是一道簡(jiǎn)單的動(dòng)規(guī)題目，同步更新數(shù)組解決了為負(fù)數(shù)的問(wèn)題。即使是求最小乘積子序列，也可以通過(guò)取和的最小值獲得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...

meteor199 2019-08-14 15:21 評(píng)論0 收藏0