求整数数组中所有子数组的和的最大值

题目：求整数数组中所有子数组的和的最大值

要求：

　　输入一个整形数组，数组中有整数也有负数。

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

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

思路：（参考王正帅的）

　　首先数组中的第一个数自己是一个数组，

　　然后从第二个开始，每个数有两种隶属可能：

　　　　　　1.和前边的子数组是一个数组，如果当前数加上前边数组的和，加起来大于当前数。

　　　　　　2.自己是一个新的数组，如果当前数加上前边数组的和，加起来小于当前数。

　　然后遍历一遍数组，将所有可能是最大子数组的子数组和存到相应子数组的最后一个位置。

　　最后遍历，得出最大的子数组和。

代码：（参考王正帅）

package com.me.array;

import java.util.Scanner;

public class ArrayMax {
    
    public static void main(String[] args) {
        int a[] = new int [100];
        @SuppressWarnings("resource")
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入数组长度");
        int len = sc.nextInt();
        System.out.println("请输入"+len+"个数字");
        for(int i=0;i<len;i++) {
            a[i] = sc.nextInt();
        }
        int max = maxSubSum(a,len);
        System.out.println("所有子数组的和的最大值为:"+max);
        
    }
    static int maxSubSum(int[] a,int length) {
        int i=0;
        int len = length;
        for(i=1;i<len;i++){
            if(a[i]+a[i-1]>a[i]) {
                a[i]=a[i]+a[i-1];
            }
        }
        int ans=-100000;
        for(i=0;i<len;i++) {
            if(ans<a[i]) {
                ans = a[i];
            }
        }
        return ans;
    } 
}

运行的结果：

总结：

真的是很久没练习java了，上个学期全都学习javaweb了，也就忽略了java的基础思维了。所以以后一定要多加练习才是。