本文主要是介绍leetcode 2321.拼接数组的最大分数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：dp
这道题其实确实是有点难想，而且是很难联想到做法的那种。（需要有一定的经验才行）但是如果说有了思路，其实就很简单了。
我们可以在草纸上画上一下。比如，我们以第一个数组为基准，我们换出的数组就是nums1[left].....nums1[right]，换入的数组就是nums2[left]....nums2[right]。
把nums1的元素总和称为sum1,那么在交换数组的元素之后我们就得到了新的元素和sum=sum1-(nums1[left]+...nums[right])+(nums2[left]....nums[right])。
我们把上面这个式子去一下括号，按照索引下标相同的原则进行合并可以得到：
sum=sum1+(nums2[left]-nums1[left])+(nums2[left+1]-nums1[left+1])+...+(nums2[right[-nums2[right])
我们把nums2[]-nums1[]这种形式新定义一个数组就是diff，nums2[left]-nums1[left]=diff[left]这么记作。
那么上面这个式子就进一步变成了：sum=sum1+diff[left]+...diff[right].
OK，到这里，相信大家会想到有一点思路，我们是不是在前面做过最大子数组和的题目呢？我们其实是不是可以把diff数组里面的最大子数组和提取出来然后和sum1相加不就是交换之后的最大和了嘛？是的，就是这样，所以我们再对diff进行动规操作。
上面只是基于对nums1进行操作的，我们还有nums2，所以这样的操作进行两次就行，然后取最大值就行了。
上代码：
class Solution {
public:int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {int n=nums1.size();vector<int>dp(n+1,0);int sum1=0;int sum2=0;vector<int>diff1;vector<int>diff2;for(int i=0;i<n;i++){sum1+=nums1[i];sum2+=nums2[i];diff1.push_back(nums2[i]-nums1[i]);diff2.push_back(nums1[i]-nums2[i]);}int max1_dp=0;int max2_dp=0;int max1=INT_MIN;int max2=INT_MIN;for(int i=0;i<n;i++){max1_dp=max(max1_dp,0)+diff1[i];max2_dp=max(max2_dp,0)+diff2[i];max1=max(max1,max1_dp);max2=max(max2,max2_dp);}return max(sum1+max1,sum2+max2);}
};这篇关于leetcode 2321.拼接数组的最大分数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
