8.6 Subarrays - Challenges | Questions asked by Top MNC's | C++ Placement Course

[Nikhilsharma-dptw]

TimeStamps :
0:11 SubArray intro
0:45 print all subarrays
3:23 max subArray sum - bruteforce - O(n^3)
6:12 max subArraySum - cumulative sum approach - O(n^2)
11:50 maxSubArraySum - Kadanes Algorithm - O(n)
16:22 max circularSubArraySum - Kadanes
24:43 pair sum problem - O(n^2)
27:40 pair sum problem - O(n)

[anaskaratela]

⭐ REQUEST⭐
PLEASE DO DRY RUN WHILE EXPLAINING THE CONCEPT PLZ..

[prathamshah]

At 8:29 for O (n^2) we can use-
int sum=0;
int mx=INT_MIN;
for(int i=0;i<n;i++) {
sum=0;
for(int j=i;j<n;j++) {
sum+=a[j];
cout<<sum;}
mx=max(mx, sum) ;
}
cout<<mx;

[Lotrhandler]

This is the exact level of questions which are actually asked in placements, so please don't lower the bar, this is exactly what is useful and needed.

[raghavtiwari]

ma'am please also use dry run for explaining the workflow of code it helps a lot in understanding

[ashutoshkashyap]

Maximum subarray sum : Improved code.
Just use the code for finding the all possible subarrays and store and compare their sum with each other to find the max. At the end of i loop print the max sum.
#include<bits/stdc++.h>

using namespace std;

int main(){

int n;
cin>>n;

int arr[n];
for(int i = 0; i<n; i++){
cin>>arr[i];
}

int j=0; int curr = 0; int prev = 0; int ans=0, mx=0;
for(int i = 0; i<n; i++){
curr = 0;
for(j = i; j<n; j++){
curr = curr + arr[j]; //adding subarray elements
prev = curr;
//comparing previous sum with the current sum
ans = max(prev, ans);
}
}
cout<<ans;
return 0;
}

You're Welcome.

[FahimBhatti]

One of the easiest code to find the maximum sum of all possible subarrays is:
#include<iostream>
using namespace std;

int main (){
int arr[4] = {-1, 4, 7, 2}, n=4, maxsum=0;

for (int i = 0; i < n; i++)
{
int sum=0;

for (int j = i; j < n; j++)
{
sum = sum+arr[j];
if (maxsum<sum)
{
maxsum = sum;
}

}
}
cout<<maxsum;

return 0;
}

There are two nested loops, so time complexity will be n square.

[harshchauhan]

Hey, just a suggestion, maximum subArray sum code is slightly difficult for any beginner, instead of current sum approach you can also go fir this easy approach with TC o(n^2) :
void maximumSubarraysum(int a[], int n){
int sum=0;
int maxj=INT_MIN;
for(int i=0; i<n; i++){
sum=0;
for(int j=i; j<n; j++){
sum+=a[j];
maxj=max(maxj, sum);
}
}
cout <<"\nMaximum sum of subarray: "<< maxj;
}

[sandeshwar]

You are an amazing teacher didi, Now I realize the quality of this course, it's really worth it; it's giving knowlege more than the paid courses...thanks aman bhaiya !😍

[SastaDopamines]

One advice to DIDI please go through some amount of testcases and do provide link to similar question in description 😇, where we can practice too😁😁😁😁

[sohammukherjee_]

THIS IS SOME REAL GOOD THANKS TO THE TEAM FOR PROVIDING THIS LEVEL OF CONTENT FOR ABSOLUTELY FREE

[revoabhi]

This is an easier approach to Maximum Subarray Sum:

#include "bits/stdc++.h"
using namespace std;

int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}

int maxSum = INT_MIN;
int sum = 0;

for(int i=0;i<n;i++)
{
sum=0;
for(int j =i;j<n;i++)
{
sum+=arr[j];
maxSum = max(maxSum, sum);
}
}
cout<<maxSum<<endl;
return 0;
}

I hope this helps <3
But Kaden's algorithm is pretty easy to understand so if we focus a bit more we will be able to understand.

[shutstart]

Suggestion for the Kadance algorithm (which gives the correct result for an array with only negative integers):
for(int i=0;i<n;i++){
currsum+=arr[i];
maxSum = max (maxSum, currsum);
if(currsum<0)
currsum=0;
}
NOTE: THE ONLY CHANGE HERE IS THAT THE POSITION OF ASSIGNING THE VALUE OF maxSum HAS CHANGED AND maxSum IS NOTHING BUT THE LARGEST NON POSITIVE INTEGER

Thank you Apna college and aman bhaiya and all the faculties for coming up with such amazing videos!

[avinash]

Here is the brute force approach for O(n^2).

#include <iostream>
#include <limits.h>
using namespace std;

int main()
{
int n;
cin>>n;

int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}

int maxim=INT_MIN;
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=i;j<n;j++)
{
sum+=arr[j];
maxim=max(maxim, sum);
}
}
cout<<maxim;
return 0;
}

[shivammaurya]

Best explanation ever thank u mam and aman bhaiya😍

[himanshuOtakuu]

15:43 I think the code is wrong for the case where all values are negative.
the maxsum=max(maxsum, currentsum); should come before the if condition

#include<bits/stdc++.h>
using namespace std;
int main(){
int n=8;
int a[] = {-2, -3, -4, -1, -2, -1, -5, -3};
int currentsum=0;
int maxsum =INT_MIN;
for(int i=0;i<n;i++){

currentsum+=a[i];
maxsum=max(maxsum, currentsum);

if(currentsum<0)
currentsum=0;
}
cout<<maxsum;
}

correct me if I am wrong

[shivambajpeyi]

I did in this way for Maximun Circulr subarray sum //brute: using kadane algo
#include "bits/stdc++.h"
using namespace std;

int main(){
int n, m;
cin >> n;
m = 2*n-1;
int arr[n];
int arr_cir[m];
//taking input for array and fill starting element in circular array
for(int i=0; i<n; i++)
{
cin >> arr[i];
arr_cir[i+1-1] = arr[i]; // 0 to <n
if(i<n-1) //m = 2n-1
{
arr_cir[i+n] = arr[i]; // n to <m
}

}

int sum=0, mx = INT_MIN;
for(int i=0; i<m; i++)
{
sum += arr_cir[i];
if(sum<0)
{
sum = 0;
}
mx = max(mx, sum);
}
cout<<mx<<endl;

return 0;
}
it has passed both the cases: 1st 4 -4 8 -6 10 -11 12 & 2nd 4 -4 6 -6 10 -11 12

[tusharpathade]

For maximum possible sum of subarray. We don't need to use cumulative sum array.

Just use this lines in inner for loop

sum += arr[j];
maxSum = max(maxSum, sum);


And at the starting of outer loop set sum=0; every time.

In this we can reduce space complexity too. 🙂

[QuransGems-zdjd]

the cumulative sum makes much more sense when I am not watching this at night being a sleepyhead, moreover coming from a mathematics' background where they teach you cumulative frequency curve in O levels, this is a much more understandable and faster approach. Thanks!

[rounakghosh]

Honestly speaking, it's very difficult to keep up the pace at which Apni Kaksha teaches 😅