首页 > > 程序设计 > Java技术 >

最大子数组和问题

2020-04-02 16:05:41来源：博客园阅读 ()

最大子数组和问题

题目描述：最大子数组和问题

1.元素个数不超过100个，存储在文本文件中。

2.元素具有首尾相接特点。

3.输出结果：

　　（1）求出的最大子数组和

　　（2）该字数组在原数组中的位置（起始下标和结束下标）

代码如下：

package com.company;

import java.io.*;
import java.util.Scanner;

public class A {

    public static int[] method01(File file){
        System.out.println("请输入少于100个数：");
        Scanner sc = new Scanner(System.in);
        String str = sc.next().toString();//输入字符串  例如输入：1,-5,9,-2,3
        String[] s = str.split(",");//以符号“,”为分割线，将分割后的内容一次存入字符数组s中 例如：此时字符串数组s中的内容为：{"1","-5","9","-2","3"}，字符串数组长度为5
        int[] array = new int[s.length];//生成一个与字符数组同等长度的整型数组，用于存储将字符串转换为整型的内容
        if(s.length >= 100){
            System.out.println("你输入的数多于100个！");
            return null;
        }
        System.out.println("你输入的数组是：");
        for (int i = 0;i < s.length;i++){
            array[i] = Integer.parseInt(s[i]);//这一步是逐一将字符串转化为整型，以便于返回值的返回 例如：此时的array数组的内容为：{1,-5,9,-2,3}
            System.out.print(s[i]+" ");
        }
        System.out.println();
        //进入写操作的函数内
        method02(file,str);
        return array;//将处理好的数组返回给调用者
    }

    public static void method02(File file,String str){
        BufferedWriter out = null;
        try{
            /*
            FileOutputStream fos = new FileOutputStream(file,true);
            OutputStreamWriter osw = new OutputStreamWriter(fos);
            out = new BufferedWriter(osw);
             */
            out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file,true)));
            out.write(str+"\r\n");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }finally {
            try {
                out.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args){
        File file = new File("D:\\IntelliJIDEA2019\\javaProject1\\src\\com\\company\\a.txt");//在指定路径下生成一个a.txt
        int[] array = null;
        array = method01(file);
        if(array != null){
            B b = new B();
            b.MSA(array,array.length);//最后调用核心算法实现功能
        }
    }
}

package com.company;

public class B {
    public void MSA(int[] a,int len){
        int cur = 0;
        int max1 = a[0];
        int start = 0;
        int end = 0;
        for (int i = 0;i < len;i++){
            if(cur < 0){
                cur = 0;
                start = i;
                end = i;
            }
            cur += a[i];
            if(cur > max1){
                max1 = cur;
                end = i;
            }
        }
        System.out.print("最大字串为："+max1+"，下标从"+start+"到"+end+"(从0开始)");
    }
}