[1,-2,3,10,-4,7,2,-5]
[3,10,-4,7,2]
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18，故返回[3,10,-4,7,2]
[1]
[1]
[1,2,-3,4,-1,1,-3,2]
[1,2,-3,4,-1,1]
经分析可知，最大子数组的和为4，有[4],[4,-1,1],[1,2,-3,4],[1,2,-3,4,-1,1]，故返回其中长度最长的[1,2,-3,4,-1,1]
[-2,-1]
[-1]
子数组最小长度为1，故返回[-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;
}
} 
class Solution {
public:
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
int former = array[0],cur=0;
//长度为1，直接返回该数组
if(array.size()==1) return array;
int res = array[0];
int pos=0;
//找到终点
for(int i=1;i<array.size();i++){
cur = max(former+array[i],array[i]);
former=cur;
if(cur>=res){
res = cur;
pos=i;
}
}
int ans=0;
int start = 0;
//找起点
for(int i=pos;i>=0;i--){
ans+=array[i];
if(ans==res){
start=i;
}
}
vector<int>result(array.begin()+start,array.begin()+pos+1);
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);//左闭右开
}
} 
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindGreatestSumOfSubArray (int[] array) {
// write code here
int n=array.length;
int[] dp=new int[n];
dp[0]=array[0];
int max=dp[0],start=0,end=1,temp=0;
for(int i=1;i<n;i++){
if(dp[i-1]+array[i]<array[i]){
dp[i]=array[i];
temp=i;
}else{
dp[i]=dp[i-1]+array[i];
}
if(dp[i]>=max){
max=dp[i];
start=temp;
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) {
// 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 {
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);
}
} class Solution: def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]: # write code here maxval = array[0] temp = array[0] # 序列累加 endindex = 1 beginindex = 0 for i in range(1, len(array)): if temp < 0: temp = array[i] beginindex = i else: temp += array[i] if temp >= maxval: endindex = i maxval = temp # begin > end 表示 序列全为负 # begin不断累加， 但此时end已保存最大值索引 if beginindex > endindex: return array[endindex:endindex + 1] return array[beginindex:endindex + 1]
public int[] FindGreatestSumOfSubArray(int[] array) {
if (array == null || array.length == 0) {
return array;
}
int max = array[0], start = 0, end = 0;
int sum = array[0], start_tmp = 0, end_tmp = 0;
for (int i = 1; i < array.length; i++) {
if (sum >= 0) {
sum = sum + array[i];
end_tmp = i;
} else {
sum = array[i];
start_tmp = i;
end_tmp = i;
}
if (sum >= max) {
max = sum;
start = start_tmp;
end = end_tmp;
}
}
int[] res = new int[end - start + 1];
for (int i = 0; i < res.length; i++) {
res[i] = array[start + i];
}
return res;
} # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param array int整型一维数组 # @return int整型一维数组 # class Solution: def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]: # write code here dp = [i for i in array] start,end = 0,1 max_start,max_end = 0,1 # max_sum = 0 # df1 = [list(i) for i in array] for i in range(1,len(array)): dp[i] = max(dp[i-1]+array[i],array[i]) if dp[i-1]+array[i] >= array[i]: end += 1 else: start,end = i,i+1 if sum(array[start:end]) > sum(array[max_start:max_end]): max_start,max_end = start,end if sum(array[start:end]) == sum(array[max_start:max_end]): if len(array[start:end])> len(array[max_start:max_end]): max_start,max_end = start,end else: max_start,max_end = max_start,max_end return array[max_start:max_end]
public int[] FindGreatestSumOfSubArray (int[] array) {
// write code here
if (array.length == 0) return new int[] {};
int startSum = 0, startSumMax = 0, endIndex = 0, endSum = 0, endSumMax = 0,
startIndex = array.length - 1;
boolean isPositive = true, isNegative = true;
int maxVal = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] >= 0)
isNegative = false;
else
isPositive = false;
maxVal = Math.max(maxVal, array[i]);
startSum += array[i];
endSum += array[array.length - 1 - i];
if (startSum >= startSumMax) {
startSumMax = startSum;
endIndex = i;
}
if (endSum >= endSumMax) {
endSumMax = endSum;
startIndex = array.length - 1 - i;
}
}
if (isNegative) return new int[] {maxVal};
if (isPositive) return array;
ArrayList<Integer> res = new ArrayList<>();
// 找到最佳开始位置
int maxStartIndex = 0, sum = 0, sumMax = 0;
for (int i = endIndex; i >= 0; i--) {
sum += array[i];
if (sum >= sumMax) {
sumMax = sum;
maxStartIndex = i;
}
}
int minEndIndex = array.length - 1, sum2 = 0, sumMax2 = 0;
for (int i = startIndex; i <= array.length - 1; i++) {
sum2 += array[i];
if (sum2 >= sumMax2) {
sumMax2 = sum2;
minEndIndex = i;
}
}
// 组装返回值
if (sumMax > sumMax2)
for (int i = maxStartIndex; i <= endIndex; i++)
res.add(array[i]);
else {
for (int i = startIndex; i <= minEndIndex; i++)
res.add(array[i]);
}
int[] result = new int[res.size()];
for (int i = 0; i < result.length; i++)
result[i] = res.get(i);
return result;
} 
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
int n = array.size();
int dp[n];
int count[n]; //计数数组，用来统计每个位置连续子数组的长度
vector<int> ans;
count[0] = 1;
dp[0] = array[0];
for(int i = 1; i < n; i++) {
if(array[i] > dp[i-1] + array[i]) {
dp[i] = array[i];
count[i] = 1;
} else {
dp[i] = dp[i-1] + array[i];
count[i] = count[i-1] + 1;
}
}
int k = 0;
for(int i = 0; i < n; i++) {
if(dp[i] > dp[k]) {
k = i;
}
if(dp[i] == dp[k]) {
k = count[i] > count[k] ? i : k;
}
}
for(int i = k - count[k] + 1; i <= k; i++) {
ans.push_back(array[i]);
}
return ans;
}
}; 
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindGreatestSumOfSubArray (int[] array) {
int start = 0;
int end = 0;
int max = Integer.MIN_VALUE;
int len = array.length;
int temp = 0;
int dpI = 0;
int dpIPre = array[0]; //dp[]数组变成dpI和dpIPre
for (int i=1; i<len; i++) {
/**
* dp[]表示包含array[i]的最大子段和, 分两种情况
* 1. dpIPre + array[i] < array[i]时，去掉dp[i-1], 保留当前array[i]
* 2. 在之前子串的情况下，继续增加array[i]
*/
if (dpIPre + array[i] < array[i]) {
dpI = array[i];
temp = i;
} else {
dpI = dpIPre + array[i];
}
if (dpI >= max) {
max = dpI;
start = temp;
end = i;
}
// 将dp[i-1]赋值成dp[i], 继续loop
dpIPre = dpI;
}
return Arrays.copyOfRange(array, start, end+1);
}
} 
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
// 时间复杂度O(N)，空间复杂度O(1)
int dp0 = array[0], dp1, res = array[0], i = 0, l = 0, r = 0;
for (int j = 1; j < array.size(); ++j) {
dp1 = max(dp0 + array[j], array[j]);
if (dp0 + array[j] < array[j]) i = j;
if (dp1 > res || (dp1 == res && j - i > r - l)) {
res = dp1;
l = i;
r = j;
}
dp0 = dp1;
}
vector<int> vec;
for (int j = l; j <= r; ++j) vec.push_back(array[j]);
return vec;
}
}; 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;
}
} 
public int[] FindGreatestSumOfSubArray(int[] array) {
List<Integer> key = new ArrayList<>();
key.add(array[0]);
List<Integer> res = new ArrayList<>();
res.add(array[0]);
int keyCode = array[0];
int keyRes = array[0];
for (int i = 1; i < array.length; i++) {
if (keyCode + array[i] >= array[i]) {
keyCode = keyCode + array[i];
} else {
keyCode = array[i];
key.removeAll(key);
}
key.add(array[i]);
if (keyRes < keyCode) {
keyRes = keyCode;
res = new ArrayList<>(key);
}
if (keyRes == keyCode){
if (key.size()>res.size()){
res = new ArrayList<>(key);
}
}
}
int[] arrayRes = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arrayRes[i] = res.get(i);
}
return arrayRes;
} class Solution: def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]: n = len(array) dp = [0] * n # 前i的最大连续子数组和 dp[0] = array[0] max_sum = array[0] left,right = 0,0 res_l,res_r = 0,0 for i in range(1,n): right += 1 # 状态转移方程 dp[i] = max(dp[i-1]+array[i],array[i]) # 更新left if dp[i-1]+array[i] < array[i]: left = i # 更新最大值&nbs***bsp;最大区间 if dp[i] > max_sum&nbs***bsp;(dp[i] == max_sum and (right-left)>(res_r-res_l)): max_sum = dp[i] res_r = right res_l = left return array[res_l:res_r+1]
class Solution: def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]: result=[] curSum=0 maxSum=0 begin=0 for i in range(len(array)): if curSum<0: curSum=array[i] begin=i else: curSum+=array[i] if curSum>maxSum&nbs***bsp;(curSum==maxSum and i+1-begin>len(result)): maxSum=curSum result=array[begin:i+1] if result==[]: return [max(array)] else: return result
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
