一、题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
二、题目分析
- 如果给定的数字都是正数，则直接相加就可以
- 如果给定的数组都是负数，则需要找出其中一个最大的数字
- 如果给定的数组既有正数又有负数，则需要进行以下操作：
如果我当前的总数是小于0的（sum1也就是负数），则总数（sum1）直接等于当前的数字。
如果我当前的总数是大于0的，则总数（sum1）加上当前的数字。
每次都需要更新最大的数，判断当前的总数是不是最大的数字
int sum1 = 0 int sum2 = array[0]; for (int i = 0; i < array.length; i++) { if (sum1 < 0) { sum1 = array[i]; } else { sum1 += array[i]; } if (sum1 > sum2) { sum2 = sum1; } }
三、题目代码
package offer; /* * (重点)连续子数组的最大和 */ public class Test29 { public static void main(String[] args) { int[] input = new int[] { 2, 8, 1, 5, 9 }; int max = FindGreatestSumOfSubArray(input); System.out.println(max); } public static int FindGreatestSumOfSubArray(int[] array) { int sum1 = array[0]; // 添加的子数组和 int sum2 = array[0]; // 最大的子数组和 if (array.length == 1) { return array[0]; } else { for (int i = 0; i < array.length; i++) { if (sum1 < 0) { sum1 = array[i]; } else { sum1 += array[i]; } if (sum1 > sum2) { sum2 = sum1; } } return sum2; } } public static int FindGreatestSumOfSubArray1(int[] array) { int count = array.length; int[] list = new int[count]; for (int i = 0; i < count; i++) { if (i == 0 || list[i - 1] <= 0) { list[i] = array[i]; } else { list[i] = array[i] + list[i - 1]; } } int max = list[0]; for (int i = 1; i < list.length; i++) { if (max < list[i]) { max = list[i]; } } return max; } }
