MAX SUM SUBARRAY OF SIZE K

A couple of weeks about I joined a MeetUp group called NYC Coders.

Here’s what they’re about from their MeetUp page:

What we’re about

We are a community of developers prepping for coding interviews, participating in hackathons, building portfolio projects, and attending software engineering panels TOGETHER. No coder is an island, and you don’t have to be one either.

In the past we’ve had App Academy, Fullstack Academy, Grace Hopper, Flatiron, New York Code + Design, General Assembly++ grads sit alongside our self-taught programmers and computer science majors to hack at projects, crack algos, and speak to software engineers from companies like Coinbase and Bloomberg. Check out footage from our inaugural panel event:

NYC Coders — 2019 Software Engineering Panel

**We are language-agnostic**

Join us on Discord where we share LinkedIn Profiles, send out tips and tricks to navigate the job search, and send out Meetup events first so you can get first dibs on RSVPing.

Want to sponsor an event or host one of our meetups at your company? Reach out to Talia Fayaz.

I’ve been a part of other groups, but this group, so far, I totally enjoy this group!

Here’s what we worked on in the last MeetUp.

Max Sum Subarray of size K

Given an array of integers Arr of size N and a number K. Return the maximum sum of a subarray of size K.

Example 1:

Input: N = 4, K = 2

Arr = [100, 200, 300, 400]

Output: 700

Explanation: Arr3 + Arr4 =700, which is maximum.

Example 2:

Input:N = 4, K = 4

Arr = [100, 200, 300, 400]

Output: 1000

Explanation: Arr1 + Arr2 + Arr3 + Arr4 =1000, which is maximum.

Your Task:

You don’t need to read input or print anything. Your task is to complete the function maximumSumSubarray() which takes the integer k, vector Arr with size N, containing the elements of the array and returns the maximum sum of a subarray of size K.

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(1)

Constraints:

1<=N<=105

1<=K<=N

// { Driver Code Starts

//Initial Template for javascript

“use strict”;

process.stdin.resume();

process.stdin.setEncoding(“utf-8”);

let inputString = “”;

let currentLine = 0;

process.stdin.on(“data”, (inputStdin) => {

inputString += inputStdin;

});

process.stdin.on(“end”, (_) => {

inputString = inputString

.trim()

.split(“\n”)

.map((string) => {

return string.trim();

});

main();

});

function readLine() {

return inputString[currentLine++];

}

function main() {

let t = parseInt(readLine());

let i = 0;

for (; i < t; i++) {

let [N, K] = readLine()

.trim()

.split(“ “)

.map((x) => parseInt(x));

let Arr = readLine()

.trim()

.split(“ “)

.map((x) => parseInt(x));

let obj = new Solution();

let res = obj.maximumSumSubarray(K, Arr, N);

console.log(res);

}

}

// } Driver Code Ends

//User function Template for javascript

/**

* @param {number} K

* @param {number[]} Arr

* @param {number} N

* @return {number}

*/

class Solution {

maximumSumSubarray(K, Arr, N) {

//code here

}
}

So, going off of the examples that were shared during the MeetUp on Zoom, this is what I tried out:

class Solution {

maximumSumSubarray(K, Arr, N) {

//code here

let s = 0;

let sum = 0;

let maxSum = 0;

for (let i = 0; i < Arr.length; i++){

sum += Arr[i];

if (i >= K-1) {

maxSum = Math.max(sum, maxSum);

sum -= Arr[start];

s++;

}

}

return maxSum

}}

Here is a brief explanation.

Given an array of integers Arr of size N and a number K. Return the maximum sum of a subarray of size K.

1. Arr is the array that contains N amount of numbers

a. So an array can look like this:

i. [1, 2, 3, 4] N = 4

* So the size of N is 4.

ii. [23, 34, 45, 56, 67, 78, 89, 90] N= 8

* So the size of N is 8.

** K is the size of the subarray.

a. A subarray is an array within an array.

b. So for an array like this below

i. [1, 2, 3, 4] N = 4

* So, a subarray can be between 1 and 4:

** A K = 3 can be [1, 2, 3] or [2, 3, 4].

ii. [23, 34, 45, 56, 67, 78, 89, 90] N= 8

* So, a subarray can be between 1 and 8:

** A K = 4 can be [23, 34, 45, 56] or [34, 45, 56, 67] or [45, 56, 67, 78]

a. So on and so forth.

3. s is initialized.

4. sum is initialized.

5. maxSum is initialized.

6. Used a for loop to iterate through the array

7. If i is less than the length of the Arr, then iterate i by 1.

8. If i is less than the length of the Arr, then iterate i by 1 and store value of Arr[i] at the index i of Arr into sum.

a. At the beginning, sum was initialized to 0.

9. If i is greater than or equal to K — 1, then execute the following

a. Using Math.max(), store the greater value between sum and maxSum into maxSum.

i. At the beginning, maxSum was initialized to 0.

b. Subtract Arr[start] from sum and store it in sum.

i. At the beginning, start was initialized to 0.

ii. Increment start by 1.

10. After the loop has iterated through Arr, then return maxSum

11. maxSum should return the maximum sum of a subarray of size K.

Trying to learn algos on your own is quite difficult.

I’d say it’s also quite difficult learning algos with a group/club/gathering that doesn’t feel right for you.

I tell you, I don’t remember ever signing up to NYC Coders on MeetUp, I think I might’ve done it on LinkedIn or an email or something BUT the main thing is, I am so thankful for this happy accident.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Josh Raiborde

Josh Raiborde

Hello, I am a young enthusiastic Software Engineer. Looking forward to an opportunity to use my skills for mutual benefits and growth as well.