一道面试题，看看如何求解最好
日期：2014-05-20 浏览次数：20644 次
一道面试题，看看怎么求解最好
给定一个数组，当中有正负数，求当中的一段“子数组”（即任意长度，连续的数字），使得这个“子数组”的和是所有“子数组”和中最大的，
如给定的数组为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的典型结构给出代码：
给定一个数组，当中有正负数，求当中的一段“子数组”（即任意长度，连续的数字），使得这个“子数组”的和是所有“子数组”和中最大的，
如给定的数组为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);
}
}
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
