最大连续和

  【问题描述】

   对于一个具有n个元素的整型数组 a，求具有最大连续和的子数组（最少具有一个元素）。

  【输入形式】

   输入的第一行为一个整数 n，接下来的一行为 n 个整数，表示数组的元素。

  【输出形式】

   输出具有最大连续和的子数组的起始编号和结束编号(数组编号为0~n-1)。

  【样例输入】

8
3 -5 1 5 -4 12 0 -1

  【样例输出】

  2 5

解题思路

  题目要求：寻找给定数组中具有最大连续和的子数组的起始和结束位置

1. 从命令行读取数组的长度和元素：n，a[n]

2. 初始化变量：

   1. int maxSoFar=a[0]; 迄今为止最大连续子数组的和

   2. int maxEndingHere=a[0]; 以当前元素结尾的最大连续子数组的和

   3. start、end：起始位置、结尾位置

   4. s：临时变量，用于更新最大连续子数组和的开始位置

3. 遍历数组：i从1开始遍历（因为第一个元素已用于初始化）

   1. 对于每个元素，判断maxEndHere + a[i] < a[i]，即判断将其加入到当前子数组中是否会使得子数组的和增大。

      1. 如果直接使用当前元素的值比加上之前的maxEndHere还大，说明从当前元素开始的子数组可能会有更大的和，于是更新maxEndHere为当前元素的值，并更新起始位置s。

      2. 否则，maxEndHere加上当前元素，继续向下遍历

   2. 判断maxEndHere > maxSoFar，即判断是否找到了一个更大的子数组和。如果是，更新maxSoFar，更新起始和结束位置的start和end。

4. 输出起始和结束位置的start和end，中间空格用“”双引号。

Java代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//命令行键入n个整数int n = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}//变量初始化int maxSoFar = a[0], maxEndHere = a[0]; //maxSoFar：迄今为止最大的子数组和；maxEndHere：以当前元素结尾的最大字数组和int start = 0, end = 0; //最大子数组和的起始位置和结束位置int s = 0; //临时变量，用来记录以当前元素结尾的最大子数组和的起始位置//循环遍历判断for (int i = 1; i < n; i++) { //i从1开始是因为a[0]已经用于初始化if(maxEndHere + a[i] < a[i]){ //如果直接使用当前元素的值比加上之前的maxEndingHere还大，说明从当前元素开始的子数组可能会有更大的和maxEndHere = a[i]; //更新maxEndingHere为当前元素的值s = i; //记录下这个可能的新起始位置s}else{maxEndHere += a[i];}if(maxEndHere > maxSoFar){ //判断是否找到了一个更大的子数组和maxSoFar = maxEndHere; //是：更新maxSoFarstart = s; //更新记录最大子数组起始和结束位置的start和end。end = i;}}System.out.println(start + " " + end);scanner.close();}
}