給定一個(gè)整數(shù)數(shù)組茄螃，找到一個(gè)具有最大和的子數(shù)組杠娱，返回其最大和廷区。
注意事項(xiàng)
子數(shù)組最少包含一個(gè)數(shù)
您在真實(shí)的面試中是否遇到過這個(gè)題嬉挡？
Yes
樣例
給出數(shù)組[?2,2,?3,4,?1,2,1,?5,3]胚迫，符合要求的子數(shù)組為[4,?1,2,1]喷户，其最大和為6
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
// 注意這種情況是，數(shù)組中至少存在一個(gè)正數(shù)的情況
int maxSubArray(vector<int> nums) {
// write your code here
int sum = 0;
int max_sum = 0;
int max_pos_begin = 0;
int max_pos_end = 0;
int begin = 0;
int end = 0;
int flag = 0;
//考慮到全部都是負(fù)數(shù)的情況
int neg_flag = 0;
int max_neg = nums[0];
int max_neg_index = 0;
for (int i = 0; i < nums.size(); i++) {
//flag 是一個(gè)標(biāo)志访锻，用來判斷begin是否已經(jīng)設(shè)置
if (nums[i] > 0&&flag==0) {
begin = i;
flag = 1;
}
sum = sum + nums[i];
if (sum < 0) {
sum = 0;
flag = 0;
}
if (sum > max_sum) {
end = i;
max_sum = sum;
max_pos_begin = begin;
max_pos_end = end;
}
if (nums[i] > 0) {
//如果存在一個(gè)正數(shù)褪尝，neg_flag就設(shè)置為1
neg_flag = 1;
}
else {
if (nums[i] > max_neg) {
max_neg = nums[i];
max_neg_index = i;
}
}
}
if (neg_flag == 1) {
return max_sum;
}
else {
return max_neg;
}
}
};
