MyException - 我的异常网
当前位置:我的异常网» J2SE » 一道面试题,看看如何求解最好

一道面试题,看看如何求解最好

www.MyException.Cn  网友分享于:2013-12-04  浏览:678次
一道面试题,看看怎么求解最好
给定一个数组,当中有正负数,求当中的一段“子数组”(即任意长度,连续的数字),使得这个“子数组”的和是所有“子数组”和中最大的,
如给定的数组为12, -8, 5, 66, -21, 0 ,35, -44,7,则最大的和的子数组为{12, -8, 5, 66, -21, 0 ,35},最大的和为89.

------解决方案--------------------
这就是个简单的典型的“动态规划”题目。

数组:x1,x2,x3,……xn
思路,首先是寻找最优子结构,这点要依靠一些经验规则。
这里的最优子结构就是
f(i)定义为以xi结尾的最大字串和。
那么f(i+1)就可以考虑
如果xi+1大于等于0或者f(i) + xi+1 > 0,那么f(i+1) = f(i) + xi+1;
如果f(i) + xi+1 <= 0,那么f(i+1) = 0;
递推公式就是有了。下面用DP的典型结构给出代码:

Java code

public class MaxSubSequence {    
    public static void main (String[] args) {
        int[] input = new int[]{3,73,-95,42,43,29,-30,-87,74,-53,22,74,-91,-1,-27,-8,-14,26,-67,-74};
        
        int[] fDp = new int[input.length];    //f for dp
        //process first element
        if (input[0] > 0)
            fDp[0] = input[0];
        for (int i = 1;i < input.length;++i){
            if (fDp[i-1]+input[i] > 0)
                fDp[i] = fDp[i-1]+input[i];
            else
                fDp[i] = 0;
        }
        //find the max value in fDp
        int maxSun = 0;
        for (int sum : fDp)
            if (sum > maxSun)
                maxSun = sum;
                
        System.out.println("max sum : " + maxSun);
    }
    
}

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有