题解 | #连续子数组的最大和(二)#
连续子数组的最大和(二)
http://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
// write code here
int res=array[0], res_start=0, res_len=1;
int cur_start=0, cur_len=1;
int n = array.size();
vector<int> dp(n, 0);
dp[0] = array[0];
for(int i=1; i<n; i++){
dp[i] = max(dp[i-1]+array[i], array[i]);
if(dp[i-1]+array[i] < array[i]){
cur_start = i;
cur_len = 1;
}
else{
cur_len += 1;
}
if(res < dp[i]){
res = dp[i];
res_start = cur_start;
res_len = cur_len;
}
else if(res == dp[i]){
if(cur_len > res_len){
res_len = cur_len;
res_start = cur_start;
}
}
}
vector<int> out;
for(int i=res_start; i<res_start+res_len; i++){
out.push_back(array[i]);
}
return out;
}
};