题解 | JZ85 连续子数组的最大和(二)
这题比上一题，增加了条件，需要我们把答案相同，最长的序列返回回来。
所以，我们不能直接两行完事了，需要在比较的时候做一下判断。
还是分为两个部分，第一部分更新dp[i]，第二部分更新ans。
在第一部分中，
sum+a[i] >= a[i]
这里特别要注意，要≥就可以更新，因为我们需要找到相同答案最长的。这是个易错点，要注意。
在第二部分中，
ans = max{dp[i], ans}
我们把之前的来的sum再和历史答案进行比较，并且还要记录位置。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
// write code here
int ans_len = 1;
int tmp_len = 1;
int pos = 0;
int ans = array[0];
int sum = array[0];
for (int i = 1; i < array.size(); i++) {
if (sum+array[i] >= array[i]) {
tmp_len ++;
sum += array[i];
} else {
tmp_len = 1;
sum = array[i];
}
if (ans < sum) {
ans = sum;
ans_len = tmp_len;
pos = i;
} else if (ans == sum) {
if (ans_len < tmp_len) {
ans_len = tmp_len;
pos = i;
}
}
}
vector<int> out;
out.assign(array.begin()+pos-ans_len+1, array.begin()+pos+1);
return out;
}
};
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型一维数组
#
class Solution:
def FindGreatestSumOfSubArray(self , a: List[int]) -> List[int]:
# write code here
ans = a[0]
sumn = a[0]
tmp_len = 1
ans_len = 1
pos = 0
for i in range(1, len(a)):
if sumn + a[i] >= a[i]:
sumn = sumn + a[i]
tmp_len += 1
else:
sumn = a[i]
tmp_len = 1
if ans < sumn:
ans = sumn
pos = i
ans_len = tmp_len
elif ans == sumn:
if ans_len < tmp_len:
ans_len = tmp_len
pos = i
return a[pos-ans_len+1:pos+1]
查看16道真题和解析
