Maximum Sum Of Three Non Overlapping Subarrays | Dynamic Programming |Leetcode 689 Solution in Hindi

NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. In this video, we discuss the solution of Maximum Sum Of Three Non-Overlapping Sub-arrays of size k. In this problem,

1. You are given an array(arr) of positive numbers and a number K.
2. You have to find the maximum sum of elements in three non-overlapping subarrays.
3. Also, you have to print indices representing the starting position of every subarray.
4. If there are multiple answers, print the lexicographically smallest one.

Expected Time Complexity - O(n)
Expected Space Complexity - O(n).



.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer

[AnkitKumar-xcrv]

Good explanation..! Understood the problem and solution in detailed from this video.

[deepknol]

very clear explanation. Thanks. Keep going!

[arnikchakraborty]

c++ code for the leetcode question 689 :

class Solution {
public:
vector<int> nums, int k) {
int n=nums.size();
vector<int> left(n, 0);
vector<int> right(n, 0);
int maxSum=0;
int leftSum=0;
int rightSum=0;
int curr=0;
int maxLeft=0;
for(int i=0;i<k;i++) curr+=nums[i];
left[k-1]=max(curr, left[k-1]);
maxLeft=curr;
for(int i=k;i<n;i++){
curr-=nums[i-k];
curr+=nums[i];
maxLeft=max(maxLeft, curr);
left[i]=maxLeft;

}

curr=0;
for(int i=n-k;i<n;i++) curr+=nums[i];
int maxRight=curr;
right[n-k]=curr;
for(int i=n-k-1;i>=0;i--){
curr-=nums[i+k];
curr+=nums[i];
maxRight=max(maxRight, curr);
right[i]=maxRight;
}

curr=0;
int ans=0;

for(int i=k;i<2*k;i++){
curr+=nums[i];
}

ans=max(ans, curr+left[k-1]+right[2*k]);

int midIdx=k;
int l=left[k-1];
int r=right[2*k];
for(int i=2*k;i<n and i+k<n;i++){
curr+=nums[i];
curr-=nums[i-k];

midIdx=i-k+1;

l=left[i-k];
r=right[i+1];
}

}

curr=0;
vector<int> temp;
for(int i=0;i<k;i++){
curr+=nums[i];
}
if(curr==l) temp.push_back(0);
else {
for(int i=k;i<midIdx;i++){
curr-=nums[i-k];
curr+=nums[i];
if(curr==l) {
temp.push_back(i-k+1);
break;
}
}
}
temp.push_back(midIdx);

curr=0;
for(int
curr+=nums[i];
}

if(curr==r){
temp.push_back(midIdx+k);
}
else {
for(int i=midIdx+2*k;i<n;i++){
curr-=nums[i-k];
curr+=nums[i];
if(curr==r){
temp.push_back(i-k+1);
break;
}
}
}



return temp;

}
};

[algorithmsbyaditi]

Awesome explanation ! so smooth and clear.

[muditjain]

After watching, it feels why its categorised as Hard Problem. Awesome explanation. Just try to increase the volume of mic.

Also, when trying to find indexes, wouldn't it be better if we use left and right arrays instead of careful indexing of prefix sum?

[girikgarg]

Is it not possible that the middle sum occurs twice in the array i.e. let's say middle sum=27 so it occurs at subarray starting from 6 as well as 9