Maximum Sum of Subarray problem — A Javascript implementaion

Image for post
Image for post
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12–5–6+50)/4 = 51/4 = 12.75

**Brute force approach**

In the below solutions we generate all (i, j): i <= j pairs and calculate the sum between. The time complexity is O(N³)

**Divide and conquer approach**

T(n) = 2*T(n/2) + O(Max_Opposite).If function “Max_Opposite” is O(n²), then T(n) = O(n²). But if we manage to make it O(n), thenT(n) = O(nlogn)
sub_left = max( sub_left.s_l, sub_left.t + sub_right.s_l )s_r = max( sub_right.s_r, sub_right.t + sub_left.s_r )t = sum( sub_left.t + sub_right.t )mx = max( s_l, s_r, t, sub_right.mx, sub_left.mx, sub_left.r+sub_right.l)

**Kadane’s algorithm**

*My Implementation of Kadane’s approach**

Image for post
Image for post

Written by

DataScience | ML | 2x Kaggle Expert. Ex Fullstack Engineer and Ex International Financial Analyst. https://www.linkedin.com/in/rohan-paul-b27285129/

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