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;
}
}