Thuật toán để tìm tổng số phần tử tối đa trong một mảng sao cho không quá k phần tử nằm liền kề

Question

Tôi đã xem qua câu hỏi này. Cho một mảng chỉ chứa các giá trị dương, bạn muốn tối đa hóa tổng các phần tử được chọn theo ràng buộc mà không có nhóm nào nhiều hơn k các phần tử được chọn liền kề. Ví dụ, nếu đầu vào là 1 2 3 1 7 9 (n = 6 và k = 2). Kết quả sẽ là 21, xuất phát từ các yếu tố chọn _ 2 3 _ 7 9. giải pháp DP đơn giản của tôi là này

#include<stdio.h> 
#include<limits.h> 
#include<malloc.h> 


long maxsum(int n,int k,long *sums){ 
    long *maxsums; 
    maxsums = malloc(sizeof(long)*n); 
    int i; 
    long add = 0; 
    for(i=n-1;i>=n-k;i--){ 
     add += sums[i]; 
     maxsums[i] = add; 
    } 

    for(i = n-k-1;i>=0;i--){ 
     int j; 
     long sum =0,max = 0,cur; 
     for(j=0;j<=k;j++){ 
      cur = sum; 
      if((i+j+1)<n) 
       cur += maxsums[i+j+1]; 
      if(cur > max) max = cur; 
      sum += sums[i+j]; 
     } 
     maxsums[i] = max; 
    } 
    return maxsums[0]; 
} 

int main(){ 
    int cases=0,casedone=0; 
    int n,k; 
    long *array; 
    long maxsum = 0; 
    fscanf(stdin,"%d %d",&n,&k); 
    array = malloc(sizeof(long)*n); 
    int i =0; 
     while(casedone < n){ 
      fscanf(stdin,"%ld",&array[casedone]); 
     casedone++; 
     } 
    printf("%ld",maxsum(n,k,array)); 
} 

Nhưng tôi không chắc chắn cho dù đây là giải pháp hiệu quả. Sự phức tạp có thể giảm thêm nữa không? Nhờ sự giúp đỡ của bạn

Answer 1

Tôi nghĩ rằng điều này sẽ làm việc:

findMaxSum(int a[], int in, int last, int k) { // in is current index, last is index of last chosen element 
    if (in == size of a[]) return 0; 
    dontChoseCurrent = findMaxSum(a, in+1, last, k); // If current element is negative, this will give better result 
    if (last == in-1 and k > 0) { // last and in are adjacent, to chose this k must be greater than 0 
     choseCurrentAdjacent = findMaxSum(a, in+1, in, k-1) + a[in]; 
    } 
    if (last != in-1) { // last and in are not adjacent, you can chose this. 
     choseCurrentNotAdjacent = findMaxSum(a, in+1, in, k) + a[in]; 
    } 
    return max of dontChoseCurrent, choseCurrentAdjacent, choseCurrentNotAdjacent 
} 

Answer 2

Mã của bạn là chính xác (ít nhất là suy nghĩ là đúng), cũng được, Cho đến nay, tôi đã không tìm thấy bất kỳ dữ liệu thử nghiệm sai. Theo suy nghĩ của bạn, chúng tôi có thể liệt kê các phương trình DP

P(v)=max{sum(C[v]~C[v+i-1])+P(v+i+1),0<=i<=k}

Trong phương trình này, P (v) có nghĩa là tối đa trong {C [v] ~ C [n]} (chúng ta để cho {C [1] ~ C [n]} là toàn bộ danh sách), vì vậy chúng ta chỉ cần xác định P (1).

Tôi chưa tìm được giải pháp tốt hơn, nhưng mã của bạn có thể được tối ưu hóa, sau khi bạn xác định P (v), bạn có thể lưu dữ liệu i, vì vậy khi bạn tìm thấy P (v-1), bạn có thể chỉ so sánh tổng (C [v-1] + C [v] ~ C [v + i-1]) + P [v + i + 1] với P [v + 1] + C [v] khi i! = k, độ phức tạp tồi tệ nhất là như nhau, nhưng độ phức tạp tốt nhất là tuyến tính.