最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

 

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

思路

数组分析：下图是我们计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。通过分析我们发现，累加的子数组和，如果大于零，那么我们继续累加就行；否则，则需要剔除原来的累加和重新开始。

过程如下：

定义状态

1 dp[i]:到i下标的时候连续的最大和

2 dp[i] = if  dp[i-1]是负数  dp[i] nums[i]

          else dp[i-1] + $num[i]

 

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max = Integer.MIN_VALUE;
        if(array == null || array.length ==0){
            return max;
        }
        if(array.length == 1){
            return array[0];
        }
        int[] dp = new int[array.length];
        dp[0] = array[0];
        max = array[0];
        for(int i =1;i<array.length;i++){
            if(dp[i-1] < 0){
                dp[i] = array[i];
            }else{
                dp[i]=dp[i-1]+array[i];
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
}

记录下标

public class Test2 {
    public static void main(String[] args) {
        int[] array ={1,-2,3,10,-4,7,2,-5};
        System.out.println(FindGreatestSumOfSubArray(array));
    }
    public static int maxSubArray(int[] array) {
        int max = Integer.MIN_VALUE;
        if(array == null || array.length ==0){
            return max;
        }
        if(array.length == 1){
            return array[0];
        }
        int[] dp = new int[array.length];
        dp[0] = array[0];
        max = array[0];
        int startIndex = 0;
        int endIndex = 0;
        for(int i =1;i<array.length;i++){
            if(dp[i-1] < 0){
                dp[i] = array[i];
                startIndex = i;
            }else{
                dp[i]=dp[i-1]+array[i];
            }
            max = Math.max(max,dp[i]);
            if(dp[i] == max){
                endIndex = i;
            }
        }
        System.out.println(startIndex + " "+ endIndex);
        return max;
    }
}

 

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            System.out.println("数组为空");
            return 0;
        }
        int sum = 0;
        long res = nums[0];
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(sum <nums[i]){
                sum = nums[i];
            }
            res = Math.max(res,sum);
        }
        if(res == 0){
            System.out.println("和为0");
        }
        return (int)res;
    }
}

 

直接法

**
 * @Auther: liuhaidong
 * Data: 2019/9/19 0019、9:45
 * Description:
 * 如果遇到小于0，直接跳出循环
 * 如果第二轮循环加第一个小于0，直接跳出循环
 * 如果不小于0 ，和最大值对比，保留最大值
 * @version: 1.0
 */

public class maxSubArray {
    public static void main(String[] args) {
        System.out.println("请输入数组");
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] nums =str.substring(1,str.length()-1).split(",");
        int[] num = new int[nums.length];
        for(int i =0;i<nums.length;i++){
            num[i] = Integer.parseInt(nums[i]);
        }
        System.out.println(maxSubArray(num));
    }

    public static int maxSubArray(int[] nums) {
        int max =0;
        //记录当前的最大值
        for(int i =0;i<nums.length;i++)
        {
            if( i ==0){
                max = nums[i];
            }

            int imax =0;

            //如果i是负数，直接退出
            if(nums[i] < 0){
                if(nums[i] > max){
                    max = nums[i];
                }
                continue;
            }
            imax =nums[i];
            if(imax > max)
            {
                max = imax;
            }
            for(int j =i+1;j<=nums.length -1;j++){
                if((imax +nums[j])<0)
                {
                    break;
                }else {
                    imax =imax + nums[j];
                    //和相加
                    if(imax >max){
                        max = imax;
                    }
                }
            }
        }
        return max;
    }