今天看到一个京东的java数组面试题,原题如下:
给定一个数组 int[] num = {-1,2,7,-9,3,6,8,2,-10};【数组不是固定的,是任意数组这只是个例子】 要求: 将数组中任意连续的项求和的最大值,并输出新的数组。 举例:3+6+8+2 = 19,在没有任何连续的想加大于19,所以输出 [3,6,8,2],最大和:19 。 请用Java输出。
public static String FindGreatestSumOfSubArray(int[] array) { if (array.length==0 || array==null) { return "数组不能为空"; } int currentSum = 0; //存储当前连续n项的和 int max = 0; //存储连续子元素和的最大值 int end = 0 ; //结束下标 int stats = 0; //起始下标 for (int i = 0; i < array.length; i++) { //核心部分,好好理解. if(currentSum<=0){ //如过当前连续n项的和小于等于0,则没必要与后面的元素相加 currentSum = array[i]; //currentSum重新赋值 }else{ currentSum += array[i]; //如果currentSum的值大于0,则继续与后面的元素相加, } if(currentSum>max){ //每次改变currentSum的值都有与max进行比较 max = currentSum; //如果currentSum的值大于max,则将currentSum的值赋值给max end = i; } } //临时变量对比最大总和使用 int temp = 0; for (int i=end; i>=0; --i) { temp+=array[i]; if (temp == max) { stats = i; } } return max+","+stats+","+end; } public static void main(String[] args) { int[] array = {6,-3,-2,7,-15,1,2,2}; String result = FindGreatestSumOfSubArray(array); String[] split = result.split(","); System.out.println(String.format("最大合%s,开始下标%s,结束下标%s",split[0],split[1],split[2])); }欢迎大家互相分享