Kadane Thuật toán số âm

Question

int array[] = {-1, 4, -2, 5, -5, 2, -20, 6}; 

Nếu tôi có mảng đó, Kadane thuật toán thực hiện của tôi để tìm subarray tối đa hoạt động:

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); 

Tuy nhiên, nếu tôi có một mảng của tất cả các âm:

int array[]= {-10, -10, -10}; 

Nó sẽ không hoạt động, nó phải trả về -10, nhưng tôi nhận được 0.

Làm cách nào để tôi cũng có thể làm việc cho số âm?

Cảm ơn bạn!

Answer 1

Theo Wikipedia, Thuật toán của Kadane yêu cầu ít nhất một số dương, do đó, tất cả các mảng phủ định của bạn là đầu vào không hợp lệ.

Answer 2

Khi tất cả các yếu tố này là tiêu cực, các mảng con tối đa là mảng con trống, trong đó có tổng 0.

Nhưng nếu bạn muốn thay đổi thuật toán để lưu trữ các phần tử lớn nhất trong trường hợp này, bạn có thể làm như sau:

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); 

Answer 3

Nếu tất cả các phần tử đều âm, thì trả lại số âm ít nhất. Trong tất cả các trường hợp khác, giải pháp của bạn sẽ hoạt động tốt.

printf("%d\n",max(max_so_far, *max_element(array,array+size))); 

Answer 4

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); 

Nó có thể làm việc

Answer 5

Hãy là một bổ sung nhỏ để algo Kadane của. Lấy cờ, are_all_elements_negative (được đặt thành true) và int (lưu trữ số nguyên cao nhất) trong khi lặp qua mảng, nếu bạn tìm thấy số dương, hãy đặt cờ sai. Trong khi cờ là đúng, lưu trữ chữ số cao nhất. Cuối cùng, hãy kiểm tra cờ, nếu cờ là đúng, xuất ra số nguyên -ve, đầu ra khác là đầu ra của đầu ra của Kadane thông thường.

Answer 6

Thuật toán của Kadane cũng không hoạt động đối với trường hợp khi tất cả các phần tử của mảng là số âm. Nó chỉ trả về 0 trong trường hợp đó. Trong trường hợp nếu bạn muốn cho việc xử lý này, chúng tôi cần phải thêm giai đoạn phụ trước khi thực hiện thực tế. Giai đoạn sẽ xem xét nếu tất cả các số là tiêu cực, nếu họ là nó sẽ trả lại tối đa của họ (hoặc nhỏ nhất về giá trị tuyệt đối).

tôi có thể đề nghị một thực hiện

#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; 
} 

vẫn còn triển khai khác tùy thuộc vào những người cần.

Answer 7

Tôi đến muộn với bữa tiệc này, nhưng có gì đó giống như tác phẩm này?:

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; 

Answer 8

Tôi nghĩ rằng đây sẽ làm việc: -

int maxSub(vector<int> x){ 
    int sum=x[0],local_max=0; 
    for(int i=0;i<x.size();i++){ 
     local_max+=x[i]; 
     if(sum < local_max) 
      sum=local_max; 
     if(local_max <0) 
      local_max=0; 
    } 
return sum; 

}

Answer 9

Nếu tất cả các yếu tố này là tiêu cực, Return phần tử lớn nhất theo giá trị

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; 

Answer 10

Nó hoạt động với mã dưới đây.

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; 
} 

Answer 11

Vui lòng tham khảo thuật toán wikiped kadane của 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;  
} 

Và nó sẽ trở lại -10 trong trường hợp của bạn