刘亦菲大尺度床戏视频,杨幂叫老公视频在线观看

題目英文

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

題目中文

給定一個(gè)整數(shù)數(shù)組 nums，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例 1:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

示例 2:

輸入: [-2,1],
輸出: 1

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

算法實(shí)現(xiàn)

利用暴力算法：

public class Solution {
    public int MaxSubArray(int[] nums) {
        int len = nums.Length;
        if (len == 0)
            return 0;
        if (len == 1)
            return nums[0];
        int max = int.MinValue;

        for (int i = 0; i < len; i++)
        {
            int sum = nums[i];
            if (sum > max)
            {
                max = sum;
            }
            for (int j = i + 1; j < len; j++)
            {
                sum += nums[j];
                if (sum > max)
                {
                    max = sum;
                }
            }
        }
        return max;        
    }
}

利用動態(tài)規(guī)劃：

動態(tài)規(guī)劃的最優(yōu)子結(jié)構(gòu)為：max[i] = Max(max[i-1] + nums[i], nums[i])

public class Solution {

    public int MaxSubArray(int[] nums) {
        int len = nums.Length;
        if (len == 0)
            return 0;
        if (len == 1)
            return nums[0];
        int[] max = new int[len];
        max[0] = nums[0];
        int result = max[0];
        for (int i = 1; i < len; i++)
        {
            if (max[i - 1] + nums[i] > nums[i])
            {
                max[i] = max[i - 1] + nums[i];
            }
            else
            {
                max[i] = nums[i];
            }

            if (max[i] > result)
            {
                result = max[i];
            }
        }
        return result;      
    }
}

實(shí)驗(yàn)結(jié)果