最大和子数组，使得每个元素都小于或等于 X

Question

给定一个有N个整数的数组A，我们需要找到子数组的最高和，使得每个元素小于或等于给定的整数X

示例：设 N=8 且数组为 [3 2 2 3 1 1 1 3] 。现在，如果 x=2，那么如果我们考虑 1 个基本索引，则通过求和 A[2] A[3] 来回答 4。如何在 O（N） 或 O（N*logN） 中执行此问题

目前，我通过检查每个可能的子阵列来采用O（N^2）方法。如何降低复杂性？

Answer 1

O（n）C代码：

const int INF = 2147483647;
int A[] = {3,2,2,3,1,1,1,3};
int ArraySize = 8;

int X = 2;



int max = -INF; //currenly max
int si = -1; //starting index
int ei = -1; //ending index
int tmax = 0; //temp currenly max
int tsi = -1; //temp starting index
int tei = -1; //temp ending index


for (int i = 0;i<ArraySize;i++) {
    if (A[i]<=X) {
        tmax+=A[i];
        if (tsi==-1) tsi = i;
    }
    else {
        tei = i-1;
        if (tmax>max) {
            max = tmax;
            si = tsi;
            ei = tei;
        }
        tsi = -1;
        tei = -1;
        tmax = 0;
    }
}
cout<<"Max is: "<<max<<" starting from "<<si<<" ending to "<<ei<<"\n";

Answer 2

我只是给你一个简单的循序渐进的方法

1. Input array=A[1..n] and x be the element and ans= -INF

（最小整型值）

2. Take another array B[1..n]={0,0,...0}.

3. For i=1 to n 
    if(A[i]<=x)
     B[i]=1;

sum=0;
4. For i=1 to n
    if(B[i])
    sum+=A[i];
    else
    {
    ans=maximum of(sum,ans);
    sum= 0;
    }
5. ans is the output.

Note ans= -INF;(smallest int value)
     sum=0;

1. for(i=1;i<=n;i++)
   //get input Ai in variable a(temporary int variable to store the elements)
   if(a<=x)
    sum+=a
   else
   {
    ans=max of (ans,sum);
    sum= 0;
   }

2. ans will be the output.

Answer 3

你可以利用这样一个事实，如果某个数组只包含小于或等于< code>X的整数，那么它的所有子数组也有这个属性。让我们为每个索引< code>i找到子数组的最大可能和，结束于< code > I (< code > sub _ sum )。

sub_sum[i] = 0, if array[i] > X
sub_sum[i] = max(array[i], sub_sum[i - 1] + array[i]), otherwise

初始条件为：

sub_sum[1] = 0, if array[1] > X
sub_sum[1] = max(array[1], 0), otherwise

您可以使用上面的公式在一个循环中计算所有< code>sub_sum值。您的问题的答案是< code>sub_sum数组中的最大值。计算复杂度为O(n)。