Java算法-求最大和的子数组序列

时间:2022-03-03 13:14:20

问题:有一个连续数组,长度是确定的,它包含多个子数组,子数组中的内容必须是原数组内容中的一个连续片段,长度不唯一,子数组中每个元素相加的结果称为子数组的和,现要求找出和最大的一个子数组。

具体算法如下:

方法一(最优算法):分治法

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]+"  ");
        
        
    }

}