连续子数组的最大和(二)

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int[] FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        ArrayList<int[]> arrDp = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            int maxSum = getMaxSum(array, i, dp, arrDp);
            dp[i] = maxSum;
            if (maxSum > max) max = maxSum;
        }

        int point = 0;
        int ct = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] == max) {
                int len = arrDp.get(i)[1] - arrDp.get(i)[0];
                if (len > ct) {
                    point = i;
                }
            }
        }
        List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
        List<Integer> resultList = list.subList(arrDp.get(point)[0], arrDp.get(point)[1] + 1);
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }

    private int getMaxSum(int[] array, int cur, int[] dp, ArrayList<int[]> arrDp) {

        if (cur == 0) {
            dp[0] = array[0];
            arrDp.add(new int[] {0, 0});
            return array[0];
        }

        if ( cur >= 1 && (dp[cur - 1]  >= 0) ) {
            arrDp.add(new int[] {arrDp.get(cur - 1)[0], cur});
        }

        if (cur >= 1 && (dp[cur - 1]  < 0)) {
            arrDp.add(new int[] {cur, cur});
        }

        return Math.max(dp[cur - 1] + array[cur], array[cur]);
    }
}

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

     * @param array int整型ArrayList 
     * @return int整型ArrayList
     */
    public int[] FindGreatestSumOfSubArray (int []array) {
 
        int dp[] = new int[array.length];
        int res = array[0];
        int left = 0;
        int realL = 0;
        int right = 0;
        int temp = 0;
        dp[0] = array[0];
        for(int i = 1; i < array.length; i++){
            dp[i] = Math.max(dp[i - 1] + array[i],array[i]);
            if(dp[i - 1] + array[i] >= array[i]){
                right = i;
  
            }else{
                left = i;
               
                right = i;
            }
            if(dp[i] >= res){
                if((right - left < temp && dp[i] > res) || right - left >= temp){
                    temp = right - left;
                    realL = left;
                }
                res = dp[i];
            }        
}
       // write code here
        int resArray[] = new int[temp + 1];
        for(int i = 0; i <= temp; i++){
            resArray[i] = array[realL++];
        }
        return resArray;
    }
}

判断条件简洁版

import java.util.*;

public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        int max = array[0], sum = array[0], begin = 0, len = 1, ansB = 0, ansL = 1;
        for(int i = 1; i < array.length; i++) {
            // sum < 0 的判断等同于dp的max判断，sum小于0才开始重新计算初始点
            if(sum < 0) {
                sum = array[i];
                begin = i;
            }else {
                sum += array[i];
            }
            if(max <= sum) {
                // 计算此时子串长度
                len = i - begin + 1;
                // 小于sum必更新数据，等于时，需判断此时的长度是否是最长的
                if(max < sum || len >= ansL) {
                    ansL = len;
                    ansB = begin;
                }
                max = sum;
            }
        }
        int[] ans = new int[ansL];
        for(int j = 0,i = ansB; i < ansB + ansL; i++, j++) {
            ans[j] = array[i];
        }
        return ans;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int x = array[0];
        int y = 0;
        int maxsum = x;

        int left = 0, right = 0;
        int max_l = 0, max_r = 0;
        for (int i = 1; i < array.length; i++) {
            right++;
            y = Math.max(x + array[i], array[i]);
            //新起点
            if (x + array[i] < array[i]) {
                left = i;
            }
            if (y >= maxsum ) {
                maxsum = y;
                max_l = left;
                max_r = i;
            }
            x = y;
        }
        return Arrays.copyOfRange(array, max_l, max_r + 1);

    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int sum = array[0];
        int res = array[0];
        int maxIndex = -1;
        int count = 1;
        int maxCount = 1;
        int start = 0;
        if(array.length<2){
           return array;
        }
        for(int i=1;i<array.length;i++){
            if(array[i]+sum>=array[i]){
                sum = array[i]+sum;
                count++;
                if(count>maxCount)
                    maxCount = count;
                if(sum>res){//后续出现了更大的连续数组，修改终点
                    res = sum;
                    maxIndex = i;
                }else if(sum==res&&count>(maxIndex-start)){//当前连续数组值等于最大的选长的，并且修改起点
                    maxIndex = i;
                    start = maxIndex - count +1;
                }  
            }else{//不能连续,修改起点
                start = i;
                count = 1;
                sum = array[i];
                if(sum>res){//再次判断当前连续数组
                    res = sum;
                    maxIndex = i;
                }
            }
        }
        if(maxIndex==-1){// 意外情况1：全是负数或者一个正数导致maxIndex没有赋值，直接排序找最大的值
            Arrays.sort(array);
            int[] result = new int[1];
            result[0] = array[array.length-1];
            return result;
        }
        if(start>maxIndex){//意外情况2：全是负数，第一个比较小，因为不连续时，又判断了sum和res，maxIndex为最大的负数
            int[] result = new int[1];
            result[0] = array[maxIndex];
            return result;
        }
        //两种意外情况都是调试后解决的 完！！
        int[] result = Arrays.copyOfRange(array,start,maxIndex+1);
        return result;
    } 
}

    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int n = array.length;
        if(n == 0) return new int[0];
        int[] dp = new int[n + 1]; 
        int l = 0, r = 1; // r使用的是开区间，r = 1代表从array[0]开始
        int max = array[0]; // 最大值初始化为array[0];
        int start = 0, end = 1; // 结果集的区间，使用左闭右开区间。初始值为array[0], 所以end初始化为1
        for(; r <= n; r++) {
            dp[r] = Math.max(dp[r - 1] + array[r - 1], array[r - 1]);
            
            if(dp[r] > max || (dp[r] == max && r - l > end - start)) {
                max = dp[r];
                end = r;
                start = l;
            } 
            
            if(dp[r] < 0) { // 注意这个if不能和上面的if交换位置
               l = r;
            }
        }
        return Arrays.copyOfRange(array, start, end);
    }

• 根据示例1显示，有两处地方需要注意：分别是从[1,-2,3]和[3,10],这两个区间最大和都发生了变动。

    区间[1,-2,3]最大和是从1到3，最大和区间的左边界发生了变动，从下标0到2；而子数组[3,10]虽然最大和从3到13，但是最大和区间的左边界没有发生变动，依然在下标2。
故，需要做一个判断识别是否需要变动当前最大和左边界下标，判断条件可以为上一个数组元素的最大和是否小于0。
    
    如果小于0，表示当前数组元素最大值为自身值，当前最大和左边界下标为当前元素的下标；
    
    如果大于0，表示最大和为在上一个元素最大和的基础上累计当前元素值，整个数组最大和的左边界下标不需要变动。

• 解答本题使用了四个下标，分别是数组最大和左右下标和当前最大和左右下标。
• 如果当前最大和大于数组最大和，则修改最大和左右下标为当前最大和的左右下标。依次遍历数组直至结束后根据左右下标获取最大和子数组。

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        if(array.length <= 1) return array;
        int n = array.length;
        int[] dp = new int[n];
        int max = array[0];
        dp[0] = array[0];
        int start = 0;
        int end = 0;
        int startLong = 0;
        int endLong = 0;
        for(int i = 1;i<n;i++){
            if(dp[i-1] + array[i] >= array[i]){
                dp[i] = dp[i-1] + array[i];
                end = i;
            }else{
                dp[i] = array[i];
                start = i;
                end = i;
            }
            if(dp[i] == max) {
                if(end - start > endLong - startLong) {
                startLong = start;
                endLong = end;
                }
            }
            //如果较大则直接赋值
            if(dp[i] > max) {
                max = dp[i];
                startLong = start;
                endLong = end;
            }
        }
        return Arrays.copyOfRange(array,startLong,endLong+1);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        //end[i]表示为i为结尾的子数列最大和, start[i]表示为i为结尾的最大子数列的第一个下标
        int[] startIndex = new int[array.length];
        int[] endVal = new int[array.length];
        startIndex[0] = 0;
        endVal[0] = array[0];
        int max = array[0];
        int maxFisrt = 0;
        int maxLast = 0;
        for (int i = 1; i<array.length; i++) {
            if (endVal[i-1] >= 0) {
                endVal[i] = endVal[i-1] + array[i];
                startIndex[i] = startIndex[i-1];
            }
            else {
                endVal[i] = array[i];
                startIndex[i] = i;
            }
            if (endVal[i] >= max) {
                max = endVal[i];
                maxFisrt = startIndex[i];
                maxLast = i;
            }
        }
        int[] result = new int[maxLast-maxFisrt+1];
        for (int i = 0; i <= maxLast-maxFisrt; i++) {
            result[i] = array[i + maxFisrt];
        }
        return result;
    }
}

import java.util.*;


public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {

      int max = -101;
      //子数组的起始位置和结尾位置
      int start = 0, end = 1;
      //cur: 以array[i]结尾的最大子串; tmp: 子串起始下标
      int cur = 0, tmp = 0;
      for(int i = 0; i <array.length; i++){
        if(cur >= 0){
          cur += array[i];
        }else{
          cur = array[i];
          tmp = i;
        }
        if(cur >= max){
          max = cur;
          start = tmp;
          end = i + 1;
        }
      }
      return Arrays.copyOfRange(array, start, end);
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {

        int maxLeft = 0, maxRight = 0;    // 记录最大和左右下标
        int curLeft = 0, curRight = 1; // 记录当前最大和左右下标
        int count = array[0],max = array[0]; 
        while(curRight < array.length){
            int curCount = count + array[curRight];
            
            if(curCount < array[curRight]){
                curLeft = curRight;
                count = array[curRight];
            } else {
                count = curCount;
            }
            // 当前是最大值，记录下左右下标
            if(count >= max){
                max = count;
                maxLeft = curLeft;
                maxRight = curRight;
            }
            curRight++;
        }
        int result[] = new int[maxRight-maxLeft+1];
        for(int i=maxLeft;i<=maxRight;i++){
            result[i-maxLeft] = array[i];
        }
        return result;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int [] dp=new int[array.length];
        dp[0]=array[0];
        int res=dp[0];
        int left;
        int r;
        for (int i = 1; i < array.length; i++) {
            if (dp[i-1]>0){
                dp[i]=dp[i-1]+array[i];
            }else {
                dp[i]=array[i];
            }
            res=Math.max(res,dp[i]);
        }


         for ( r = dp.length - 1; r >= 0; r--) {
            if (dp[r]==res){
                break;
            }
        }//找出右边---题目要求最长，所以是倒叙开始找
        for (left= r-1; left >= 0; left--) {
            if (dp[left]<0){
              break;
            }
        }//找出左边--从r-1开始，因为dp[left]<0才跳出循环，此时left已经找到了dp[]第一个值为负数的位置
       return Arrays.copyOfRange(array,left+1,r+1);//左闭右开
        
    }
}

public class Solution {
 
    public int[] FindGreatestSumOfSubArray (int[] array) {
        if(array.length==1){
            return array;
        }
        // write code here
        //字串的开始索引  默认从0开始
        int low=0;
        //字串的结束索引
        int high=0;
        //字串的和
        int  sum=array[0];
        //当前数组字串的和
        int  max=sum;
        //临时值，记录重新加的时候的
        int  temp=0;
        for(int i=1;i<array.length;i++){
                //字串加上数组的当前值后，比没加上的要大，则加上该值。
               if(sum+array[i]>=array[i]){
                     //计算和
                   sum+=array[i];
               }else{
                   //加上之后还比这个值要小，字串直接从这个点开始，继续比较之后的和
                   sum=array[i];
                   temp=i;
               }
            //加上该数组的值后，和比最大记录和要大，移动high指针到当前数的数组下标
            if(sum>=max){
                //记录新的最大值
                max=sum;
                //移动最大字串的结束位置。
                high=i;
                //记录字串开始的位置
                low=temp;
            }
        }
        int[]  res=new int[high-low+1];
        for(int i=0;i<high-low+1;i++){
              res[i]=array[i+low];
        }
        return  res;
    }
}