C++ || Easiest Explanation || Prefix Sum + Two pointer  + Greedy Approach
\n# Complexity\n- Time complexity : O(N)\n\n- Space complexity : O(N)\n\n# Code\n\nclass Solution {\npublic:\n\n    typedef long long ll;\n\n    const ll M = 1e
\n# Complexity\n- Time complexity : O(N)\n\n- Space complexity : O(N)\n\n# Code\n```\nclass Solution {\npublic:\n\n    typedef long long ll;\n\n    const ll M = 1e9 + 7;\n\n    ll mod(ll a){\n        return ((a%M)+M)%M;\n    }\n    ll mul(ll a,ll b){\n        return mod(mod(a)*mod(b));\n    }\n    ll add(ll a,ll b){\n        return mod(mod(a)+mod(b));\n    }\n\n    vector<ll>calc_prefix_sum(vector<int>&nums){\n        int n = nums.size();\n        vector<ll>psum(n,0LL);\n        psum[0] = (ll)nums[0];\n        for(int i=1;i<n;i++){\n            psum[i] = psum[i-1] + (ll)nums[i];\n        }\n        return psum;\n    }\n\n    vector<ll>calc_suffix_sum(vector<int>&nums){\n        int  n = nums.size();\n        vector<ll>ssum(n,0LL);\n        ssum[n-1] = (ll)nums[n-1];\n        for(ll i=n-2;i>=0;i--){\n            ssum[i] = ssum[i+1] + (ll)nums[i];\n        }\n        return ssum;\n    }\n\n    int maxSum(vector<int>& nums1, vector<int>& nums2) {\n\n        int m = nums1.size();\n        int n = nums2.size();\n\n        vector<pair<int,int>>critical;\n\n        nums1.push_back(1e9);\n        nums2.push_back(1e9);\n        nums1.insert(nums1.begin(),0);\n        nums2.insert(nums2.begin(),0);\n\n        m+=2;\n        n+=2;\n\n        int i=0,j=0;\n\n        while(i<m && j<n){\n            if(nums1[i] > nums2[j]){\n                j++;\n            }\n            else if(nums1[i] < nums2[j]){\n                i++;\n            }\n            else{\n                critical.push_back({i,j});\n                i++;\n                j++;\n            }\n        }\n\n        nums1[m-1] = 0;\n        nums2[n-1] = 0;\n\n        vector<ll>prefix1 = calc_prefix_sum(nums1);\n        vector<ll>prefix2 = calc_prefix_sum(nums2);\n\n        ll maximum_sum = 0LL;\n        int sz = critical.size();\n\n        for(int i=0;i<sz-1;i++){\n            int i1 = critical[i].first;\n            int j1 = critical[i].second;\n            int i2 = critical[i+1].first;\n            int j2 = critical[i+1].second;\n            ll path1 = prefix1[i2] - prefix1[i1];\n            ll path2 = prefix2[j2] - prefix2[j1];\n            maximum_sum += max(path1,path2);\n        }\n\n        return mod(maximum_sum);\n\n    }\n};\n\n/*\n\n1 3 5 7 9\n3 5 100\n\n2 4 5 8 10\n4 6 8 9\n\nWe can switch between these two arrays as many times as we want.\n\nGoal : Maximum score of the path by toggling between two arrays if possible.\n\nMoves : nums1[i] == nums2[j]  i-->j  /  j-->i\n\nCritical Points : where nums1[i] == nums2[j]\n\n  2 4 5 8 10 -1\n    4 6 8 9  -1\n\n  6 + 14 + 10\n\n  Algorithm :\n\n  First store all the critical points in an array , critical(c)\n\n  c[k] = {i,j} pair of indices where two array elements matches with each other.\n\n  0 2 4 5 8 10 0\n  0   4 6 8 9  0\n  \n  c[0] = {0,0}\n  c[1] = {2,1}\n  c[2] = {4,3}\n  c[3] = {6,5}\n\n  we will precompute the prefix sums for both the arrays and finally we need to calculate the maximum segment in between two critical point indices .\n\n  c[i] c[i+1] c[i+2] .... \n\n*/\n```
['Array', 'Two Pointers', 'Greedy', 'Prefix Sum', 'C++']