Q53 Maximum Sum of Two Non-Overlapping Subarrays - LeetCode 1031

PHOTO

Sat Apr 01 2023 06:36:37 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

class Solution {
    
    public int function(int[] nums , int x , int y){
        //making dp 
        int n = nums.length;
        int[] dp1 = new int[n];     //dp for MSA of x size
        int[] dp2 = new int[n];     //dp for MSA of y size

        int sum1 = 0 , sum2 = 0;
        for(int i = 0 , j = n-1 ; i < n ; i++ , j--){
            int val = nums[i];
            //if ith index is smaller than x store sum only
            if(i < x){
                sum1 += val;
                dp1[i] = sum1;
            }
            //else check which is larger previous MSAx or sum including current 
            //element
            else{
                sum1 += nums[i] - nums[i-x];
                dp1[i] = Math.max(dp1[i-1] ,sum1);
            }

            int val2 = nums[j];

            //we fill 2nd array right to left 
            if(j + y  >= n){
                sum2 += val2;
                dp2[j] = sum2;
            }
            //else check which is larger previous MSAy or sum including current 
            //element
            else{
                sum2 += nums[j] - nums[j+y];
                dp2[j] = Math.max(dp2[j+1] , sum2);
            }
        }

        int ans = 0;

        //assuming x size MSA to be first and y size MSA to be 2nd
        for(int i = x-1 ; i < n-y ; i++)
        ans = Math.max(ans , dp1[i] + dp2[i+1]);

        return ans;
    }
    
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        /* Q53 dp playlist ,we use kadane's algo to find MSA for x size and y
        size respectively for every element and then take max(MSAx + MSAy)for
        all indexes

        we fill 2nd dp right to left and 1st dp left to right

        similiarly we do the same this time assuming y size has occured first 
        and then x size has occured and do the same

        finally we return max value of the two values obtained
        */
        
        //assuming firstlen exists 1st and secondlen exists 2nd
        int ans1 = function(nums , firstLen , secondLen);

        //assuming firstlen exists 2nd and secondlen exists 1st
        int ans2 = function(nums , secondLen , firstLen);

        return Math.max(ans1 , ans2);
    }
}

https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

DP level 2

@Ayush_dabas07

Q66 Distinct Echo Substrings - LeetCode 1316 (rabin karp rolling hash -> O(n^2)) Q66 Distinct Echo Substrings - LeetCode 1316(O(n^3) solution) Q65 Interleaving String - LeetCode 97 Q64 Frog Jump - LeetCode 403 Q63 Champagne Tower - LeetCode 799 Q62 Super Ugly Number - LeetCode 313 Q61 Ugly Number 2 - LeetCode 264 Q60 Minimum Insertion Steps to Make a String Palindrome - LeetCode 1316 Q59 Temple Offerings | Practice | GeeksforGeeks Q58 Word Break - LeetCode 139 Q57 Arithmetic Slices II - Subsequence - LeetCode 446 Q56 Arithmetic Slices - LeetCode 413 Q55 Max sum of M non-overlapping subarrays of size K - GeeksforGeeks (tabulization) Q55 Max sum of M non-overlapping subarrays of size K - GeeksforGeeks (memoization) Q54 Maximum Sum of 3 Non-Overlapping Subarrays - LeetCode 689 Q53 Maximum Sum of Two Non-Overlapping Subarrays - LeetCode 1031 Q52 Maximum difference of zeros and ones in binary string | Practice | GeeksforGeeks Q51 Mobile numeric keypad | Practice | GeeksforGeeks Q50 Distinct Transformation LeetCode Playground ( tabulization approach) Q50 - Distinct Transformation- LeetCode Playground ( recursion + memoization approach) Q49 Highway BillBoards - Coding Ninjas Codestudio approach 2 Q49 Highway BillBoards - Coding Ninjas Codestudio (approach 1 LIS) Q48 Knight Probability in Chessboard - LeetCode 688 Q47 Cherry Pickup - LeetCode 741 (recursion approach) Q46 Super Egg Drop - LeetCode 887 Q45 Predict the Winner - LeetCode 486 Q45 Optimal Strategy For A Game | Practice | GeeksforGeeks | leetcode 46 Q44 Largest Sum Subarray of Size at least K | Practice | GeeksforGeeks Q42 Maximum Subarray - LeetCode 53 Q41 Minimum Cost To Make Two Strings Identical | Practice | GeeksforGeeks Q40 Minimum ASCII Delete Sum for Two Strings - LeetCode 712 Q39 Scramble String - LeetCode 87 Q38 Edit Distance - LeetCode 72 Q37 Regular Expression Matching - LeetCode 10 Q36 Wildcard Matching - LeetCode Q35 Longest Repeating Subsequence | Practice | GeeksforGeeks Q34 Longest Common Substring | Practice | GeeksforGeeks Q33 Count Different Palindromic Subsequences - LeetCode 730 Q32 Number of distinct subsequences | Practice | GeeksforGeeks Q31 Longest Palindromic Substring - LeetCode Q30 Count Palindromic Subsequences | Practice | GeeksforGeeks Q29 Longest Palindromic Subsequence - LeetCode 516 Q28 Longest Common Subsequence - LeetCode 1143 Q27 Minimum Score Triangulation of Polygon - LeetCode 1039 Q26 Optimal binary search tree | Practice | GeeksforGeeks Q24 Matrix Chain Multiplication | Practice | GeeksforGeeks Q23 Palindrome Partitioning II - LeetCode 132 Q23 Palindrome Partitioning II - LeetCode - 132 ( n^3 approach) Q22 Palindromic Substrings - LeetCode 647 Q21 Rod Cutting | Practice | GeeksforGeeks Q20 Minimum Score Triangulation of Polygon - LeetCode 1039 Q19 Intersecting Chords in a Circle | Interviewbit Q18 Generate Parentheses - LeetCode 22 Q17 PepCoding | Count Of Valleys And Mountains Q16 Unique Binary Search Trees - LeetCode 96 Q15 Catalan Number Minimum Score of a Path Between Two Cities - 2492 Q14 Perfect Squares - LeetCode Q13 Russian Doll Envelopes - LeetCode (LIS in NlogN - accepted solution) Q13 Russian Doll Envelopes - LeetCode 354 solution1(LIS in O(n^2)) Q12 PepCoding | Maximum Non-overlapping Bridges Q11 Longest Bitonic subsequence | Practice | GeeksforGeeks Q10 Maximum sum increasing subsequence | Practice | GeeksforGeeks Q9 PepCoding | Print All Longest Increasing Subsequences Q8 Longest Increasing Subsequence - LeetCode 300 Q7 2 Keys Keyboard - LeetCode 650 Q-6 PepCoding | Print All Results In 0-1 Knapsack Q5 PepCoding | Print All Paths With Target Sum Subset Q4 PepCoding | Print All Paths With Maximum Gold Q3 PepCoding | Print All Paths With Minimum Cost Q2 Jump Game II - LeetCode 45 Q1 Maximal Square - LeetCode 221 Q67 Longest Increasing Subsequence - LeetCode 300 ( LIS O(nlogn) solution) Q43 K-Concatenation Maximum Sum - LeetCode 1191 Q13 Russian Doll Envelopes - LeetCode 354 ( LIS -> O(nlogn) solution) Q25 Burst Balloons - LeetCode 312

Browse more snippets >>