题解 | #连续子数组的最大和(二)#

O(N), O(N)，dp

建立一个3*N的dp数组，

dp[i][0]表示以array[i]为末尾的连续数组的最大和

dp[i][1]表示与其对应的左边索引

dp[i][1]表示与其对应的右边索引，左闭右闭

先找到最大值，然后遍历dp，找到最大值中的最长数组。

import java.util.*;
public class Solution {
//
public int[] FindGreatestSumOfSubArray (int[] array) {
    // write code here 
    
    int[][] dp = new int[array.length][3];//以array[i]结尾的最大数组连续和
    dp[0][0] = array[0];
    dp[0][1] = 0;
    dp[0][2] = 0;
    int left = 0;
    int right = 0;
    int res = array[0];
    for(int i = 1; i < array.length; i++){
        if(dp[i-1][0] >= 0){
            dp[i][0] = dp[i-1][0] + array[i];
            dp[i][1] = dp[i-1][1];
            dp[i][2] = i;
        }else{
            dp[i][0] = array[i];
            dp[i][1] = i;
            dp[i][2] = i;
        }
        res = Math.max(res, dp[i][0]);
    }
    
    int len = 0;
    for(int i = 0; i < array.length ; i++){
        if(dp[i][0] == res && (dp[i][2]-dp[i][1]+1) > len){
            left = dp[i][1];
            right = dp[i][2];
        }
    }
    
    
    int[] nums = new int[right - left + 1];
    int cur = 0;
    for(int i = left; i <= right; i++){
        nums[cur++] = array[i];
    }
    
    return nums;
}
}

O(N), O(1), 贪心 双指针

若curSum是负数，则需要tmp变量存储左指针，后面可能会用到。

import java.util.*;
public class Solution {
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
public int[] FindGreatestSumOfSubArray (int[] array) {
    // write code here 
    
    int left = 0;
    int right = 0;
    int curSum = array[0];
    int res = array[0];
    int tmp = 0;//mark
    for(int i = 1; i < array.length; i++){
        if(curSum >= 0){
            curSum += array[i];
            if(res <= curSum){//小于等于
                left = tmp;
                right = i;
                res = curSum;
            } 
        }else{
            curSum = array[i];//更改左指针位置
            tmp = i;
            if(res < curSum){//小于
                res = curSum;
                left = i;
                right = i;
            }
        }
    }
    
    
    int[] nums = new int[right - left + 1];
    int cur = 0;
    for(int i = left; i <= right; i++){
        nums[cur++] = array[i];
    }
    
    return nums;
}
}