题解 | #连续子数组的最大和(二)#
连续子数组的最大和(二)
http://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21
非常简单的DP问题，现在的更改在于需要返回的时取得最大子数组和的数组并且要求不仅时局部和是最大的而且要求长度也是最长的，所以只需要将长度的更新加入到最值的更新部分就可以的。再加上返回的是数组，所以只需要引入子数组的开始下标和终止下标就可得到长度和取得最大值的数组；
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindGreatestSumOfSubArray (int[] array) {
if(array.length==1)
return new int[]{array[0]};
int len = 0;
int max_sum = Integer.MIN_VALUE;
int sum = array[0];
int start_inde = 0, start=0;
int end_index = 0,enx = 0;
for(int i=1;i<array.length;i++){
if(sum>=0){
sum += array[i];
end_index = i;
}else {
sum = array[i];
start_inde = i;
end_index = i;
}
if(max_sum<=sum){
enx = end_index;
start = start_inde;
max_sum = sum;
}
}
int[] list_array = new int[enx-start+1];
for(int i=start ,j=0;i<=enx;i++,j++){
list_array[j] = array[i];
}
return list_array;
}
}
查看12道真题和解析
