返回一个整数数组中最大子数组的和（可视化）

要求

1.输入一个整型数组，数组里有正数也有负数。

2.数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

3.求所有子数组的和的最大值。要求时间复杂度为O(n)。

4.要求输出运算过程

源代码

package one_simple;

import java.util.Scanner;

public class VisualFindMaxArray {

    public static void main(String[] args) throws InterruptedException {
        System.out.println("算法思路是首先将数组中相邻且正负相同的数相加算出数块，然后根据数块计算最大子数组的和
");
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入数组的长度:");
        int length = sc.nextInt();
        System.out.print("请输入"+length+"个数:");
        int[] a = new int[length];
        for(int i=0;i<length;i++)
            a[i] = sc.nextInt();
        sc.close();
        System.out.println();
        /*录入结束*/
        int[] b = new int[length];  //数块数组
        String[] c = new String[length];  //记录数块数组中每一个数块的组成
        for(int i=0;i<length;i++)
            c[i] = "";
        b[0] = a[0];
        c[0] = "1 ";
        int j=0,max,maxnum=0;
        for(int i=1;i<10;i++) {
            if(a[i]<0 && b[j]>0) {
                b[++j] = a[i];
                c[j] += (i+1)+" ";
            }
            else if(a[i]>0 && b[j]<0) {
                b[++j] = a[i];
                c[j] += (i+1)+" ";
            }
            else if(a[i]<=0 && b[j]<0) {
                b[j] += a[i];
                c[j] += (i+1)+" ";
            }
            else if(a[i]>=0 && b[j]>0) {
                b[j] += a[i];
                c[j] += (i+1)+" ";
            }
        }
        String[] s1,s2;
        for(int i=0;i<=j;i++) {
            s1 = c[i].split(" ");
            if(s1.length==length) {
                System.out.println("第1个数块大小为"+b[i]+",是所有数的和,则最大子数组的和为数组的最大数");
                max=a[0];
                for(i=1;i<length;i++)
                    if(max<a[i])
                        max=a[i];
                System.out.println("最大子数组的和为:" + max + ",位置为第"+(i++)+"个数");
                return;
            }
            else if(s1.length==1)
                System.out.println("第"+(i+1)+"个数块为第"+s1[0]+"个数:"+b[i]);
            else
                System.out.println("第"+(i+1)+"个数块为第"+s1[0]+"到第"+s1[s1.length-1]+"个数的和:"+b[i]);
        }
        max=b[0];
        for(int i=0;i<=j;i++)
            if(max<b[i]) {
                max=b[i];
                maxnum=i;
            }
        int t=0;
        int first = maxnum,last = maxnum;
        for(int i=maxnum;i>=2;i-=2) {    //从最大数块所在位置向左运算
            t=t+b[i-1]+b[i-2];         //最大数块左方的数块和，如果存在大于0的，则可以加入最大子数组和的运算
            if(t>0) {
                max+=t;
                first=i-2;
                t=0;
            }
        }
        t=0;
        for(int i=maxnum;i<=j-2;i+=2) {    //从最大数块所在位置向右运算
            t=t+b[i+1]+b[i+2];         //最大数块右方的数块和，如果存在大于0的，则可以加入最大子数组和的运算
            if(t>0) {
                max+=t;
                last=i+2;
                t=0;
            }
        }
        System.out.print("
最大子数组的和为:" + max);
        s1=c[first].split(" ");
        s2=c[last].split(" ");
        System.out.println(",是第"+s1[0]+"个数到第"+s2[s2.length-1]+"个数的和");
    }
}

运行截图