2022美团春招后端实习 两道题目

## 2022美团春招后端实习 两道题目
------------
小团在努力地刷题。
在刷题的过程中小团碰到了一道经典的数据结构题，即给出一个长度为n的数组，
你需要进行m次数组上的区间操作，操作包含将区间内所有数加上一个值和查询一个区间内所有数的和。
现在他想知道，如果允许重新排列初始数组中的元素并依次进行操作，则操作中所有查询区间和的答案之和能够达到多大？

输入描述  
第一行有两个数n,m(1<=n<=5000,1<=m<=500)，代表数组长度和操作次数。  
第二行有n个数，代表初始数组中的元素。  
接下来m行每行形如1 l r或2 l r k，分别代表查询下标属于[l,r]的元素之和这一操作和将下标属于[l,r]的元素全部加上一个定值k。其中l,r,k满足1<=l<=r<=n，1<=k<=5000。  
数字间两两均有空格隔开。  
样例输入  
5 5  
3 4 2 1 5  
1 1 3   
2 3 4 2  
1 2 4  
2 2 3 2  
1 3 5  
样例输出  
42  

*分析：我自己用了多次的求前缀和、差分数组进行操作。  
每次更改值做一次差分数组、修改值、还原数组、更新前缀和*
```CPP


vector<int> chafen(vector<int>&nums){
    vector<int> c;
    c.push_back(nums[0]);
    for(int i=1;i<nums.size();i++){
        c.push_back(nums[i]-nums[i-1]);
    }
    return c;
}
vector<int> qianzhuihe(vector<int>& nums){
    vector<int> qianzhui(nums.size()+1,0);
    for(int i=1;i<qianzhui.size();i++){
        qianzhui[i]=qianzhui[i-1]+nums[i-1];
    }
    return qianzhui;
}
int chaxunhe(vector<int>& qianzhuihe,int l,int r){
    return qianzhuihe[r+1]-qianzhuihe[l];
}
void jiajian_(vector<int>& chafen,int l, int r, int op){
    chafen[l] += op;
    if(r+1<chafen.size()){
        chafen[r+1] -= op;
    }
}
void huanyuan(vector<int>&nums,vector<int>&chafen){
    //通过差分数组还原目前的nums
    nums[0] = chafen[0];
    for(int i=1;i<chafen.size();i++){
        nums[i] = chafen[i]+nums[i-1]; 
    }
}
int zhuti(const vector<vector<int>>& caozuo,vector<int>& nums){
    int res = 0 ; //最终答案
    vector<int> qianzhui = qianzhuihe(nums);
    cout<<"caozuo.size()="<<caozuo.size();
    for(const auto& v : caozuo){
        //v是每个操作，根据首位确定什么操作
        int op = v[0];
        int l = v[1]-1;
        int r = v[2]-1;
        if(op==1){
            //查询l~r的和
            
            res += chaxunhe(qianzhui,l,r);
            cout<<"nums:";
            for(auto& n:nums){
                cout<<n<<" ";
            }
            cout<<endl;
            cout<<"res:"<<res<<endl;
        }
        else if (op ==2 ){
            //对l~r 区间加上x
            int val = v[3];
            vector<int> c = chafen(nums);
            jiajian_(c,l,r,val);
            huanyuan(nums,c);
            qianzhui = qianzhuihe(nums);
            cout<<"nums:";
            for(auto& n:nums){
                cout<<n<<" ";
            }
            cout<<endl;
        }
    }
    return res;
}

int main(){
    int n;//数组长度
    int m;//操作次数
    cin >>n;
    cin >>m;
    vector<int> nums(n,0);
    for(int i =0; i<n;i++) cin>>nums[i];
    vector<vector<int>> caozuo;

    // vector<int> a = qianzhuihe(nums);
    // for(auto& n : a){
    //     cout<<n<<" ";
    // }


    for(int i=0;i<m;i++){
        //先输入一个数确定是什么长度
        int op;
        cin>>op;
        if(op==1){
            vector<int> tmp(3,0);
            tmp[0] = op;
            for(int i=1;i<3;i++){
                cin>>tmp[i];
            }
            caozuo.push_back(tmp);
            continue;
        }
        else if(op==2){
            vector<int> tmp(4,0);
            tmp[0] = op;
            for(int i=1;i<4;i++){
                cin>>tmp[i];
            }
            caozuo.push_back(tmp);
            continue;
        }
    }
    // for(auto& n:caozuo){
    //     for(auto& c:n){
    //         cout<<c<<" ";
    //     }
    //     cout<<endl;
    // }

    int res = zhuti(caozuo,nums);
    cout<<"res:"<<res<<endl;
    return 0;
}
```

--------------------------------
给一个数组，你可以将其中某一段翻转，然后求连续子数组的最大和。  
输入：-1,3,-5,2,-1,3  
  
输出：7（将数组下标1-2的元素翻转，然后求得3+2+-1+3 = 7，另有别的翻转方法）  

*分析：第一次想着用全排列将该数组所有排列组合情况列出来，然后一一求连续子数组的最大和。发现这么做是不符合题意的。  
题目是翻转某一段，而全排列是所有元素任意排列，这就会导致一种极端情况，所有正整数连续排列在一起，从而得到错误的连续子数组最大和。  
翻转某一段，这一段里面的数是可以包含负数的。  
而全排列得到的答案是该数组所有正整数的和，因此还进行全排列干什么？直接一次轮询将所有正整数加起来就是了。因此全排列不可行。  
而另一种解法就是用两个for，将所有翻转情况列出来。  
对所有翻转情况进行求连续子数组的最大和，可以得到最终答案。  
因此这道题本人是这么解的：先列出所有翻转情况，然后写一个求连续子数组的最大和函数，对每个翻转情况应用这个函数，得到最终解*  
```CPP
#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;

int qiuhe_max(vector<int>& nums){
    int max_ = INT_MIN;//首先，等于自己
       for(int i =0;i<nums.size();i++)
    {
        
        int j=1;
        int res=nums[i];
        while((i+j)<nums.size()){
            res+= nums[i+j];
            j++;
            max_ = max(max_,res);
        }
        
    }
    return max_;
}

void fanzhuan(vector<int>& nums, int l, int r){
    while(l<r){
        swap(nums[l],nums[r]);
        l++;
        r--;
    }
}

int digui_fanzhuan(vector<int>& nums){
    int max_he =INT_MIN;
    for(int i=0;i<nums.size();i++){
        for(int j=i;j<nums.size();j++){
            //先求和在翻转？先翻转在求和？
            //先求和在翻转再求和。然后撤销反转。
            int he = qiuhe_max(nums);
            //翻转
            fanzhuan(nums,i,j);
            he = max(he, qiuhe_max(nums));
            max_he = max(max_he,he);
            //撤销
            fanzhuan(nums,i,j);
        }
    }
    return max_he;
}

int main(){
    int n;
    cin>>n;
    vector<int> nums;
    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        nums.push_back(tmp);
    }
    
    int max_ = digui_fanzhuan(nums);
    cout<<max_;
    return 0;
}
```
#美团笔试##实习##美团##后端开发##面经#