问题:有一个连续数组,长度是确定的,它包含多个子数组,子数组中的内容必须是原数组内容中的一个连续片段,长度不唯一,子数组中每个元素相加的结果称为子数组的和,现要求找出和最大的一个子数组。
具体算法如下:
方法一(最优算法):分治法
import java.util.Scanner; public class Second { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); System.out.println("输入数组长度"); int n=sc.nextInt(); System.out.println("输入数组数据(用空格分开)"); int i; int a[]=new int[n]; for(i=0;i<n;i++) a[i]=sc.nextInt(); int begin=0;//子数组开始下标 int end=0;//子数组结束下标 int maxValue=a[0]; int tempValue=maxValue; //for循环寻找最大和的连续子数组 for(i=1;i<n;i++) { tempValue+=a[i]; if((tempValue>a[i])&&(tempValue>maxValue)) { end=i; maxValue=tempValue; } else if(tempValue<=a[i]) { begin=i; end=i; tempValue=a[i]; } } //输出最大和的连续子数组的相关信息 System.out.println("最大子数组和为:"+maxValue+"\n子数组内容为:"); System.out.println("下标:"); for(i=begin;i<=end;i++) System.out.print(i+" "); System.out.println("\n"+"下标对应数值:"); for(i=begin;i<=end;i++) System.out.print(a[i]+" "); } }