首页 > 其他 > 详细

letcode code]Maximum Subarray

时间:2015-04-02 22:06:16      阅读:226      评论:0      收藏:0      [点我收藏+]

1 题目:

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.

click to show more practice.

 

Hide Tags
 Divide and Conquer Array Dynamic Programming
 
2 分析:
要找最大连续的子数组。好吧,动态规划题,想了半天,想不出递推式怎么写,可能与做的太少有关。只分析出求F(n)的话,有两种情况,一种是F(n-1)最大子串里面有A[n-1],一种没有,然后我就不知道怎么写了。。。看了看别人的代码,分析了一下,定义一个curSum,取肯定有A[i]的最大子串,然后比较maxSum与curSum就行了。
标记函数可以将
 maxSum = Math.max(maxSum, curSum);
改为if语句,存开始序号和子串长度。
 
3 代码:
    public int maxSubArray(int[] A){
        if (A.length == 0) {
            return 0;
        }
        int maxSum = A[0];
        int curSum = A[0];
        int len = A.length;
        for (int i = 1; i < len; i++) {
            curSum = Math.max(curSum + A[i], A[i]);
            maxSum = Math.max(maxSum, curSum);
        }
        return maxSum;
    }

 

letcode code]Maximum Subarray

原文:http://www.cnblogs.com/lingtingvfengsheng/p/4388324.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!