int array[] = {-1, 4, -2, 5, -5, 2, -20, 6};
如果我有那个数组，我的 Kadane 算法实现来找到最大子数组就可以了：
int max_so_far = INT_MIN;
int max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max(max_ending_here + array[i], 0);
max_so_far = max(max_ending_here, max_so_far);
}
printf("%d\n", max_so_far);
但是，如果我有一个包含所有负数的数组：
int array[]= {-10, -10, -10};
它不起作用，它应该返回 -10，但我得到 0。
我怎样才能让它也适用于负数？
谢谢！
当所有元素都是负数时，最大子数组是空子数组，其和为 0。
但是，如果您想在这种情况下更改算法以存储最大元素，您可以执行以下操作：
int max_so_far = INT_MIN;
int max_ending_here = 0;
int max_element = INT_MIN;
for (int i = 0; i < size; i++)
{
max_ending_here = max(max_ending_here + array[i], 0);
max_so_far = max(max_ending_here, max_so_far);
max_element = max(max_element, array[i]);
}
if (max_so_far == 0)
max_so_far = max_element;
printf("%d\n", max_so_far);
根据Wikipedia，Kadane 的算法至少需要一个正数，因此您的所有负数数组都是无效输入。
int max_so_far = INT_MIN;
int max_ending_here = array[0];
for (int i = 1; i < size; i++) {
max_ending_here = max(max_ending_here + array[i], array[i]);
max_so_far = max(max_ending_here, max_so_far);
}
printf("%d\n", max_so_far);
It may works
稍微增加 Kadane 的算法。在遍历数组时取一个标志 are_all_elements_negative（设置为 true）和一个 int（存储最高的 -ve 整数），如果找到正数，则将标志设置为 false。当标志为真时，存储最高的 -ve num。最后，检查标志，如果标志为真，输出-ve整数，否则输出常规Kadane的算法输出。
那么 Kadane 的算法不适用于数组的所有元素都是负数的情况。在这种情况下，它只返回 0。如果您想要处理这个问题，我们需要在实际实施之前添加额外的阶段。如果所有数字都是负数，则该阶段将查看，如果它们是负数，它将返回其中的最大值（或绝对值的最小值）。
我可以建议一种实现
#define find_max_val(x,y) x >= y ?x :y;
int min_sum(int a[],int n){
int min_so_far = a[0],min_end_here = a[0];
for(int i = 1;i < n; i++){
min_end_here = find_max_val(a[i],min_end_here + a[i]);
min_so_far = find_max_val(min_so_far,min_end_here);
}
return min_so_far;
}
根据需要，还有其他实现方式。
如果我们有一个所有负数的数组，那么数组中的最大元素将是结果。
例如：如果数组元素是
-3 -2 -5 -4 -1
最大和子数组是-1。
只是一个 O(n) 搜索。
代码：
int maxSubArraySum(int array[], int size) {
int max_sum = INT_MIN, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here += a[i];
if (max_sum < max_ending_here) {
max_sum = max_ending_here;
}
max_ending_here = max(max_ending_here, 0);
}
return max_sum;
}
如果所有元素都是负数，则返回最小的负数。在所有其他情况下，您的解决方案都可以正常工作。
printf("%d\n",max(max_so_far, *max_element(array,array+size)) );
根据维基
public int maxSubArray(int[] nums) {
int currentSum = 0;
int bestSum = 0;
for (int element : nums) {
currentSum = Math.max(0, currentSum + element);
bestSum = Math.max(bestSum, currentSum);
}
return bestSum;
}
上面的代码将无法输入
nums = [-1]
再次根据WIKI
如果输入不包含正元素（包括输入为空时），此版本的算法将返回 0。对于不允许空子数组的问题的变体，best_sum 应初始化为负无穷大，并且在 for 循环中 current_sum 应更新为 max(x, current_sum + x)。在这种情况下，如果输入不包含正元素，则返回值是最大元素的值（即最小负值），如果输入为空，则返回负无穷大。
负输入的修改代码：
public int maxSubArray(int[] nums) {
int currentSum = 0;
int bestSum = Integer.MIN_VALUE;
for (int element : nums) {
currentSum = Math.max(element, currentSum + element);
bestSum = Math.max(bestSum, currentSum);
}
return bestSum;
}
请参考 wikiped kadane's algorithm max subarray
int max_subArray(Integer[] input){
int max_so_far,max_ending_here;
max_so_far = max_ending_here =input[0];
for(int i =1; i<input.length;i++){
max_ending_here = Math.max(input[i], input[i]+max_ending_here);
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
在你的情况下它会返回 -10
这是我的方法，使用了额外的 2 个变量
public int maxSubArray(int[] nums) {
int max_so_far = 0;
int max_ends_here = 0;
int largestNeagtive = Integer.MIN_VALUE;
boolean isAllNegativeNumbers = true;
for (int i = 0; i < nums.length; i++) {
max_ends_here += nums[i];
if (max_ends_here < 0) max_ends_here = 0;
if (max_so_far < max_ends_here) max_so_far = max_ends_here;
if (isAllNegativeNumbers && nums[i] >= 0) isAllNegativeNumbers = false;
if (nums[i] < 0 && nums[i] > largestNeagtive) largestNeagtive = nums[i];
}
return isAllNegativeNumbers ? largestNeagtive : max_so_far;
}
这是实现目标的另一种选择
int Solution::maxSubArray(const vector<int> &A){
int cs=0,ms=0,l=A.size(),x=0,min;
if(A[0]<0)
min=A[0];
x++;
if(l==1)
return A[0];
for(int i=1;i<A.size();i++){
if(A[i]<0)
x++;
if(A[i]>min)
min=A[i];
else
break;
}
if(x==l)
return min;
for(int i=0;i<A.size();i++){
cs=cs+A[i];
if(cs<0)
cs=0;
ms=max(cs,ms);
}
return ms;
}
我参加这个聚会迟到了，但是这样的事情会起作用吗？：
cur_sum = max_sum = sequence[0];
sum_to_j = 0;
for j in range(0, len(sequence)):
sum_to_j += sequence[j];
if sum_to_j > cur_sum:
cur_sum = sum_to_j;
if cur_sum > max_sum:
max_sum = cur_sum
if sum_to_j < 0:
sum_to_j = 0;
cur_sum = sequence[j];
print max_sum;
它适用于以下代码。
public int algorithmKadane(int[] input_array){
int sum = input_array[0];
int rotate_sum = input_array[0];
for(int i=1; i< input_array.length ; i++){
rotate_sum = Math.max(input_array[i], rotate_sum+input_array[i]);
sum = Math.max(rotate_sum,sum);
}
return sum;
}
public static int max_sum(int[] in){
int maxsum=0;
int cursum=0;
for (int i=0;i<in.length;i++){
cursum = in[i]+cursum;
if (cursum>maxsum) {
maxsum = cursum;
}
// for negative value
if (cursum < 0) {
for (int n=0;n<in.length;n++){
maxsum = in[n];
if (cursum>maxsum){
maxsum=cursum;
}
}
}
}
return maxsum;
}
如果所有元素都是负数，则按值返回最大的元素
boolean allNegative = true;
int bigNegative = Integer.MIN_VALUE;
int maxSum = 0;
int sum = 0;
for(int i=0;i<a.size();i++){
// if all numbers are negative
if(a.get(i)>=0){
allNegative = false;
}else{
if(a.get(i)>bigNegative){
bigNegative = a.get(i);
}
}
sum += a.get(i);
if(sum<0){
sum=0;
}
if(sum>maxSum){
maxSum = sum;
}
}
if(allNegative){
return bigNegative;
}
return maxSum;
希望这个解决方案也能处理 Kadane 算法的所有负数情况
long long int n,max_f=0,i,max_end=0,s;
cin>>n;
long long int a[n];
for(i=0;i<n;i++)
{
cin>>a[i];
}
long long int *m;
m=max_element(a,a+n);
if(*m<0)
{
s=*m;
}
else {
for(i=0;i<n;i++)
{
max_end= max_end +a[i];
if(max_end<0)
{
max_end=0;
}
if(max_f < max_end)
{
max_f=max_end;
}
s=max_f;
}
}
cout<<s<<endl;
}
int maxSub(vector<int> x){
int current_max=0,overall_max=INT_MIN;
for(int i=0;i<x.size();i++){
current_max+=x[i];
if(overall_max<current_max)
overall_max=current_max;
if(current_max <0)
current_max=0;
}
return overall_max;
}