My complex but maybe more structure solution java with memo


  • 1
    H

    To solve this question, I just think about the start index and the number of Non-Overlapping Subarrays.
    Such as the first subarray's index is i, and then later two's start index will be i + k. And we just think about the Maximum Sum of 2 Non-Overlapping Subarrays start from i + k and so on.
    One important trick is we at the first time we think about the Maximum Sum of 2 Non-Overlapping Subarrays and Maximum Sum of 1 Non-Overlapping Subarrays their length should be the maximum one so the memo will be useful. And every time later we can get answer from HashMap. So the time complex is o(n)? right?

    class Solution {
        HashMap<Integer, Integer> map2 = new HashMap();
        HashMap<Integer, int[]> map2Res = new HashMap();
        HashMap<Integer, Integer> map1 = new HashMap();
        HashMap<Integer, Integer> map1Res = new HashMap();
        public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
            countOne(nums, 2 * k, k);
            int max = 0;
            int [] res = new int[3];
            for (int i = 0; i <= nums.length - 3 * k; i++) {
                int countCur = 0;
                for (int j = 0; j < k; j++) {
                    countCur += nums[i + j];
                }
                int help = countTwo(nums, i + k, k);
                if (countCur + help > max) {
                    max = countCur + help;
                    res[0] = i;
                    res[1] = map2Res.get(i + k)[0];
                    res[2] = map2Res.get(i + k)[1];
                }
                // System.out.println("index" + i +"max" + max);
            }
            return res;
        }
        public int countTwo(int[] nums, int start, int k) {
            if (map2.get(start) != null) {
                return map2.get(start);
            }
            int max = 0;
            int [] res = new int[2];
            for (int i = nums.length - 2 * k; i >= start; i--) {
                int countCur = 0;
                for (int j = 0; j < k; j++) {
                    countCur += nums[i + j];
                }
                int help = countOne(nums, i + k, k);
                if (countCur + help >= max) {
                    res = new int[2];
                    max = countCur + help;
                    res[0] = i;
                    res[1] = map1Res.get(i + k);
                }
                map2.put(i, max);
                map2Res.put(i, res);
            }
            return max;
            
        }
        public int countOne(int[] nums, int start, int k) {
            if (map1.get(start) != null) {
                return map1.get(start);
            }
            int max = 0;
            int res = 0;
            for (int i = nums.length - k; i >= start; i--) {
                int countCur = 0;
                for (int j = 0; j < k; j++) {
                    countCur += nums[i + j];
                }
                if (countCur >= max) {
                    max = countCur;
                    res = i;
                }
                map1.put(i, max);
                map1Res.put(i, res);
            }
            return max;
        }
    }
    

    Hope it helpful


  • 0

    @huaiyan thanks for sharing your solution, it is very helpful for breaking this problem down into sub-problems to quickly and easily understand the solutions. I wrote a similar solution in C++, the variable names and the code are purposefully verbose to hopefully help others ( like me ) who struggle to understand the basics of this problem.

    Summary: slide 3 windows of size k from the left-most start positions to the right-most end positions such that the windows do NOT overlap. While sliding, keep track of the window's max sum and start index of the window. Memorize and repeat. In the end there are 3 subarrays referred to as Three, Two, and One. The left-most max-sum subarray is Three, the middle max-sum subarray is Two, and the right-most max-sum subarray is One.

    Example 1:

    nums = 012345  k=2
           332211  <-- subarrays Three, Two, and One
    
    One   = 45
    Two   = 23
    Three = 01
    

    Example 2:

    nums = 0123456789  k=2
    
    again, initially:
    
    One   = 45
    Two   = 23
    Three = 01
    
    start sliding One to find max-sum from start to end...
    
    nums = 0123456789
           332211 -->
               ^
               start for One
    
    continually slide window by 1 to find the max:
    
    nums = 0123456789
           3322 11 -->
    
    nums = 0123456789
           3322  11 -->
    
    nums = 0123456789
           3322   11 -->
    
    nums = 0123456789
           3322    11
                   ^
                   end for One
    
    Next slide Two to the next position, and check memo for already calculated max-sum positions for One...
    
    nums = 0123456789
           332211 -->
             ^
             start for Two
    
    ... repeat ...
    
    each time Two slides left by one position,
    look up  the already calculated max-sum positions for One
    
    ...
    ...
    ...
    
    nums = 0123456789
           33    2211
                 ^
                 end for Two
    
    ... repeat ...
    
    nums = 0123456789
           332211 -->
           ^
           start for Three
    
    ... repeat ...
    
    nums = 0123456789
               332211
               ^
               end for Three
    
    
    class Solution{
    private:
        unordered_map<int,int> _memoSumOfOneSubarrays{};
        unordered_map<int,pair<int,int>> _memoSumOfTwoSubarrays{};
        
        vector<int> calcSubarraySums(const vector<int>& nums){
            vector<int> sums(nums.size()+1,0);
            for (int i=1; i<sums.size(); ++i){
                sums[i]=sums[i-1]+nums[i-1];
            }
            return sums;
        }
        
        int getSubarraySum(const vector<int>& sums, int start, int k){
            return sums[start+k] - sums[start];
        }
        
        int maxSumOfOneSubarrays(const vector<int>& sums, int start, int k){
            if (_memoSumOfOneSubarrays.find(start)!=_memoSumOfOneSubarrays.end()){
                return _memoSumOfOneSubarrays[start];
            }
            int maxSumOne=0,indexOfMaxSumOne=0;
            for (int indexOne=start; indexOne < sums.size()-k; ++indexOne){
                int currSumOne=getSubarraySum(sums,indexOne,k);
                if (currSumOne > maxSumOne){
                    maxSumOne=currSumOne;
                    indexOfMaxSumOne=indexOne;
                }
            }
            for (int i=start; i<=indexOfMaxSumOne; ++i){
                _memoSumOfOneSubarrays[i]=indexOfMaxSumOne;
            }
            return _memoSumOfOneSubarrays[start];
        }
        
        pair<int,int> maxSumOfTwoSubarrays(const vector<int>& sums, int start, int k){
            if (_memoSumOfTwoSubarrays.find(start)!=_memoSumOfTwoSubarrays.end()){
                return _memoSumOfTwoSubarrays[start];
            }
            pair<int,int> res;
            int maxSumTwo=0,indexOfMaxSumTwo=start,indexOfMaxSumOne=start+k;
            for (int indexTwo=start; indexTwo < sums.size()-2*k; ++indexTwo){
                int indexOne=maxSumOfOneSubarrays(sums, indexTwo+k, k);
                int currSumTwo=getSubarraySum(sums,indexTwo,k);
                int currSumOne=getSubarraySum(sums,indexOne,k);
                if (currSumTwo+currSumOne > maxSumTwo){
                    maxSumTwo=currSumTwo+currSumOne;
                    indexOfMaxSumTwo=indexTwo;
                    indexOfMaxSumOne=indexOne;
                }
            }
            res.first=indexOfMaxSumTwo;
            res.second=indexOfMaxSumOne;
            for (int i=start; i<=indexOfMaxSumTwo; ++i){
                _memoSumOfTwoSubarrays[i]=res;
            }
            return _memoSumOfTwoSubarrays[start];
        }
        
        vector<int> maxSumOfThreeSubarrays(const vector<int>& sums, int start, int k){
            vector<int> res(3,0);
            int maxSumThree=0;
            int indexOfMaxSumThree=start,indexOfMaxSumTwo=start+k,indexOfMaxSumOne=start+2*k;
            for (int indexThree=start; indexThree < sums.size()-3*k; ++indexThree){
                auto indexTwoAndOne=maxSumOfTwoSubarrays(sums, indexThree+k, k);
                int indexTwo=indexTwoAndOne.first;
                int indexOne=indexTwoAndOne.second;
                int currSumThree=getSubarraySum(sums,indexThree,k);
                int currSumTwo=getSubarraySum(sums,indexTwo,k);
                int currSumOne=getSubarraySum(sums,indexOne,k);
                if (currSumThree+currSumTwo+currSumOne > maxSumThree){
                    maxSumThree=currSumThree+currSumTwo+currSumOne;
                    indexOfMaxSumThree=indexThree;
                    indexOfMaxSumTwo=indexTwo;
                    indexOfMaxSumOne=indexOne;
                }
            }
            res[0]=indexOfMaxSumThree;
            res[1]=indexOfMaxSumTwo;
            res[2]=indexOfMaxSumOne;
            return res;
        }
        
    public:
        vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k){
            vector<int> sums=calcSubarraySums(nums);
            return maxSumOfThreeSubarrays(sums,0,k);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.