Data Structures and Algorithms(DSA) Concept- Subarrays — Part 3.
Topics : Kadane’s Algorithm , Subarray problems solved with prefix Sum approach.
Q. 1 Using Kadane’s Algorithm find the Largest Sum Contiguous Subarray.
Lets Understand how Kadane's Algo works
lets assume A is and array of size N
Case 1 :
if all the A[i] >=0
the answer is the sum of all the elements.
Eg : A=[4, 2, 1, 6, 7]
ans =20
Case 2 :
if all the A[i]<0
A=[-4, -8, -9, -3, -5]
ans =-3 // Max of A[]
Case 3 :
parts of A[] is positive and others negative
A=[-1, -3, -2, 4, 1, 2, -7, -8]
ans = sum of all +ve numbers
Lets use what we have learnt on the following arrays.
A = [ 5, 6, 7, -3, 2, -10, -12, 8, 12, -4, 7]
sum = 5 11 18 15 17 7 0(-5) 8 20 16 23
ans = 5 11 18 18 18 18 18 18 20 20 23
A = [ -3, 6, -2, 12, -5, 2, 7, -6 ]
sum = 0(-3) 6 4 16 10 12 19 13
ans = 0 6 6 16 16 16 19 19
So from the examples we can see that if we keep calculating the sum along the
array and check if the sum is greater than the previous ans , and replace the
ans if this condition is met we will find the largest sum of a subarray.
Also every time a sum goes below 0 we re initialse the sum with 0.The code :
public long MaxSumSubarray(int[] A){
long sum=A[0];
long ans=A[0];
for(int i=1;i<A.length;i++){
if(sum<0){
sum=0;
}
sum=sum+A[i];
ans=Math.max(sum,ans);
}
return ans;
}TC : O(N)
SC: O(1)
Q2 . Given an array A of size N, in A all the variables are initialised with 0. You are given Q queries in the form of [start , value] .For every query add the value from index start to N-1.
Eg:
A [7] = [0,0,0,0,0,0,0]
Q =[
[1, 3], // 0 3 3 3 3 3 3 start at index 1 value=3
[4,-2], // 0 3 3 3 1 1 1
[3, 1], // 0 3 3 4 2 2 2 => ANS
]
We will see how we can solve this in two ways
public int[] subarrayQuestion(int[] A,int[][]Q){
int N=A.length;
// 1st Approach;
for(int i =0;i<Q.length;i++){
int start=Q[i][0];
int value=Q[i][1];
for(int j=start;j<N-1;j++){
A[j]=A[j]+value;
}
}
// TC : O(NxQ)
// A will now meet the requirment but lets see if we can bring down the TC
// 2nd Approach;
for(int i=0;i<Q.length;Q++){
int start=Q[i][0];
int value=Q[i][1];
A[start]=A[start]+value;
}
for(int i=1;i<A.length;i++){
A[i]=A[i]+A[i-1];
}
//TC : O(Q+N)
// IN this approach by using prefix sum approach we are able to get a better
// TC
}
Q 3. Given an array A of size N, in A all the variables are initialised with 0. You are given Q queries in the form of [start ,end , value] .For every query add the value from index start to end.
Eg:
A [7] = [0,0,0,0,0,0,0]
Q =[
[1, 3, 2], // 0 2 2 2 0 0 0
[2, 5, 3], // 0 2 5 5 3 3 0
[2, 4,-1], // 0 2 4 4 2 3 0
[3, 6, 2] // 0 2 4 6 4 5 2 // Ans
]public int[] subarrayQuestion(int[] A,int[][]Q){
for( int i=0;i<Q.length;i++){
int start= Q[i][0];
int end = Q[i][1];
int value= Q[i][2];
A[start]= A[start]+value;
if(end<N-1){
A[end+1]=A[end+1] -value;
}
}
for( int i=1;i<A.length;i++){
A[i]=A[i-1]+A[i];
}
return A;
//TC : O(Q+N)
}Hey I hope this was helpful to you , Please do follow and like.
Up next :
