科大讯飞🤣第七批笔试

第三题是根据条件可知最长合并的情况是1，2， 4， 8， 16，...，2^30，说明区间长度最大不会超过30，直接对每个位置dfs加记忆化搜索
int m[1e5][30];
int ps[1e5]; // 前缀和
int n;
int arr[1e5];
int dfs(l, size) {
    if(m[i][size]!=-1)return m[i][size];
    int r = i+size-1;
    int sum = ps[r+1]-ps[l];
    int ans=sum;
    if(r+1<n &amp;&amp; sum < arr[r+1]){
        ans = dfs(l, size+1);
    }
    if(l-1>=0 &amp;&amp; sum < arr[l-1]){
        ans = max(ans, dfs(l-1, size+1));
    }
    m[l][size] = ans;
    return ans;
}