CODEWITHSUNDEEP
algorithm
Mrinal
Mrinal

Reputation: 113

greatest sum sub array such that each element is less than or equal to X

Given an array A with N integers we need to find the highest sum of sub array such that each element is less than or equal to given integer X

Example : Let N=8 and array be [3 2 2 3 1 1 1 3] . Now if x=2 then answer is 4 by summing A[2] + A[3] if we consider 1 base indexing . How to do this question in O(N) or O(N*logN)

Currently am having O(N^2) approach by checking each possible subarray. How to reduce the complexity ?

Upvotes: 0

Views: 150

Answers (3)

user2736738
user2736738

Reputation: 30936

I am just giving you a simple step by step approach

Time complexity O(n) Space complexity O(n)

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

(smallest int value)

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.

Time complexity O(n) Space complexity O(1)

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.

Upvotes: 1

citxx
citxx

Reputation: 2545

You can use the fact that if some array contain integers only less than or equal to X, then all its subarrays also have this property. Lets find for each index i the greatest possible sum of subarray, ending at i (sub_sum).

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

Initial conditions are:

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

You can compute all sub_sum values in one loop using the formulas above. The answer to your question is the maximum in sub_sum array. The computation complexity is O(n).

Upvotes: 1

Hassan Abbasi
Hassan Abbasi

Reputation: 272

An O(n) C++ code:

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

Upvotes: 0

Related Questions