求数组中连续子元素的最大值
方法一：利用动态规划的思想。
public class Test2 { public static void main(String[] args) { int[] m ={3, -5, 7, 9, -1, 4, -40, 12, -2, 13, 2, -13, 10}; int currentSum = 0; int maxSum = 0; for (int i = 0; i < m.length; i++) { currentSum += m[i]; if (currentSum > maxSum) { maxSum = currentSum; } if (currentSum < 0) { currentSum = 0; } } System.out.println(maxSum); } } 方法二：将一个数组利用负数划分为几部分，然后分别比较这几部分的值 import java.util.Arrays; public class Work2 { // 获得一个数组中最大值的下标 public static int Selecete(int[] m) { int max = 0; for (int i = 0; i < m.length; i++) { if (m[max] < m[i]) { max = i; } } return max; } public static void main(String[] args) { int[] m = {3, -5, 7, 9, -1, 4, -40, 12, -2, 13, 2, -13, 10}; // 怎样动态根据不和谐负数的个数给tag分配空间？？ /* 借助辅助数组(初始为-1)，然后根据不为负数的个数动态分配空间 */ int[] tag = new int[3]; //tag数组记录m数组中不和谐负数的下标 int index = 0; // 寻找m数组中不和谐负数的下标 for (int i = 0; i < m.length; i++) { if (m[i] < 0) { if (i > 0 && (m[i] + m[i - 1]) < 0) { tag[index] = i; index++; } if (i == 0 && m[i] < 0) { tag[index] = i; index++; } } } System.out.println(Arrays.toString(tag)); // 将不和谐下标之间的数的和计算出来存储到 result 数组中 int[] result = new int[4]; //存储结果的数组 for (int i = 0; i < tag[0]; i++) result[0] += m[i]; for (int i = tag[0] + 1; i < tag[1]; i++) result[1] += m[i]; for (int i = tag[1] + 1; i < tag[2]; i++) result[2] += m[i]; for (int i = tag[2] + 1; i < m.length; i++) result[3] += m[i]; System.out.println(Arrays.toString(result)); //得到结果数组中最大值的下标、与tag数组有关联 int from = Work2.Selecete(result); // 借用tag数组、输出m中连续子元素和最大的元素的下标 System.out.println("连续子元素的下标为："); for (int i = tag[from - 1] + 1; i < tag[from]; i++) { System.out.print(i + " "); } System.out.println(); System.out.println("最大值为："); System.out.println(result[Work2.Selecete(result)]); } }