美文网首页动态规划
Leetcode53-Maximum Subarray(Pyth

Leetcode53-Maximum Subarray(Pyth

作者: LdpcII | 来源:发表于2017-09-21 19:29 被阅读0次

    53. Maximum Subarray

    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.

    题解:

    输入一个数组,求数组的连续子数组中,最大的一段的和;
    原问题:n个数的数组(nums)的最大子段和;
    子问题:
    一个数的数组的最大子段和:dp[0] = nums[0];
    两个数的数组的最大子段和:两种情况,加上第一个数(dp[0] + nums[1])或不加上第一个数(nums[1]):dp[1] = max(dp[0] + nums[1], nums[1]);其实也就相当于是以第二个数作为子段结尾的情况下的最优解;然后再取max(dp[0], dp[1])
    确认状态:
    n个数的数组的最大子段和:
    以nums[n-1]结尾的最大子段和前n-1个子段最大和比较,取最大值;
    动态规划状态转移方程:
    以第n个数结尾的最大子段和:dp[n-1] = (dp[n-2] + nums[n-1], nums[n-1])
    边界状态:dp[0] = nums[0];
    最后输出:max(dp[0],dp[1],.....dp[n-1])

    My Solution(C/C++)

    #include <cstdio>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    class Solution {
    public:
        int maxSubArray(vector<int> &nums) {
            vector<int> dp(nums.size() + 3, 0);
            if (nums.size() == 0) {
                return 0;
            }
            dp[0] = nums[0];
            int max_dp = dp[0];
            for (int i = 1; i < nums.size(); i++) {
                dp[i] = max(dp[i - 1] + nums[i], nums[i]);
                if (max_dp < dp[i]) {
                    max_dp = dp[i];
                }
            }
            return max_dp;
        }
    };
    
    int main() {
        vector<int> nums;
        nums.push_back(-2);
        nums.push_back(1);
        nums.push_back(-3);
        nums.push_back(4);
        nums.push_back(-1);
        nums.push_back(2);
        nums.push_back(1);
        nums.push_back(-5);
        nums.push_back(4);
        Solution s;
        printf("最大子段和:%d", s.maxSubArray(nums));
        return 0;
    }
    

    结果

    最大子段和:6
    

    My Solution 1(Python)

    class Solution(object):
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            sum, result = 0, 0
            for i in range(len(nums)):
                sum += nums[i]
                if sum < 0:
                    sum = 0
                else:
                    result = max(sum, result)
            if result == 0:
                return max(nums)
            return result
    

    My Solution 2(Python)

    class Solution:
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            dp = []
            if len(nums) == 0:
                return []
            dp.append(nums[0])
            max_dp = dp[-1]
            for i in range(1, len(nums)):
                dp.append(max(dp[i-1] + nums[i], nums[i]))
                if max_dp < dp[-1]:
                    max_dp = dp[-1]
            return max_dp
    
    

    Reference (转)

    Python:
    class Solution(object):
        def maxSubArray(self, nums):
            for i in xrange(1,len(nums)):nums[i]=max(nums[i], nums[i]+nums[i-1])
            return max(nums)
    
    Java:
    class Solution {
    public int maxSubArray(int[] A) {
            int n = A.length;
            int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
            dp[0] = A[0];
            int max = dp[0];
            
            for(int i = 1; i < n; i++){
                dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
                max = Math.max(max, dp[i]);
            }
            
            return max;
    }
    }
    

    相关文章

      网友评论

        本文标题:Leetcode53-Maximum Subarray(Pyth

        本文链接:https://www.haomeiwen.com/subject/vgytextx.html