开封市网站建设,建设铝合金窗网站,在线平面设计工具,支付宝手机网站签约【问题描述】 对于一个具有n个元素的整型数组 a#xff0c;求具有最大连续和的子数组#xff08;最少具有一个元素#xff09;。 【输入形式】 输入的第一行为一个整数 n#xff0c;接下来的一行为 n 个整数#xff0c;表示数组的元素。 【输出形式】 输出具有最大连续和的… 【问题描述】 对于一个具有n个元素的整型数组 a求具有最大连续和的子数组最少具有一个元素。 【输入形式】 输入的第一行为一个整数 n接下来的一行为 n 个整数表示数组的元素。 【输出形式】 输出具有最大连续和的子数组的起始编号和结束编号(数组编号为0~n-1)。 【样例输入】
8 3 -5 1 5 -4 12 0 -1 【样例输出】 2 5
解题思路 题目要求寻找给定数组中具有最大连续和的子数组的起始和结束位置 从命令行读取数组的长度和元素na[n] 初始化变量 int maxSoFara[0]; 迄今为止最大连续子数组的和 int maxEndingHerea[0]; 以当前元素结尾的最大连续子数组的和 start、end起始位置、结尾位置 s临时变量用于更新最大连续子数组和的开始位置 遍历数组i从1开始遍历因为第一个元素已用于初始化 对于每个元素判断maxEndHere a[i] a[i]即判断将其加入到当前子数组中是否会使得子数组的和增大。 如果直接使用当前元素的值比加上之前的maxEndHere还大说明从当前元素开始的子数组可能会有更大的和于是更新maxEndHere为当前元素的值并更新起始位置s。 否则maxEndHere加上当前元素继续向下遍历 判断maxEndHere maxSoFar即判断是否找到了一个更大的子数组和。如果是更新maxSoFar更新起始和结束位置的start和end。 输出起始和结束位置的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();}
}
