39. ①处应填( )
A. pre[i]=std::max(pre[i-1],a[i-1])
B. pre[i + 1]= std::max(pre[i],pre[i +1])
C. pre[i]= std::max(pre[i - 1],a[i])
D. pre[i]= std::max(pre[i],pre[i - 1])
答案:D,std::vectorpre(a + mid, a+r); 复制从a[mid]到a[r-1]的数组。然后计算这个数组的前缀最大值,即pre[i]是从0到i的数组的最大值。
40. ②处应填( )
A. a[j]< max
B. a[j]< a[i]
C. pre[j - mid]< max
D. pre[j - mid]> max
答案:B,找最大值在前半段还是后半段的分界点,比较容易混淆的是C选项,因为此时max还没有更新,所以不能让a[j]或pre[j-mid]跟max来比,只能跟a[i]来比。
41. ③处应填( )
A. (long long)(j - mid)* max
B. (long long)(j - mid)*(i - 1)* max
C. sum[j - mid]
D. sum[j - mid]*(i - 1)
答案:A,i为起点,终点在后半段, 且最大值在前半段的个数是(j-mid)个,此时最大值都是max。
42. ④处应填( )
A. (long long)(r - j)* max
B. (long long)(r - j)*(mid - i)* max
C. sum[r - mid]- sum[j - mid]
D. (sum[r - mid]- sum[j - mid])*(mid - i)
答案:C,i为起点,终点在后半段,且最大值在后半段的情况,最大值的和通过sum前缀和数组计算。
43. ⑤处应填( )
A. solve(0, n)
B. solve(0, n - 1)
C. solve(1,n)
D. solve(1, n - 1)
答案:A,因为line 12-14行,可以看到二分的结束条件是l+1==r,而且此时取l的值,也就是说[l,r),左闭右开的区间。
完善程序题2 整体解析:
分治算法,分为三部分来计算,1) 起点终点都在前半段;2) 都在后半段;3) 起点在前半段、终点在后半段。前两部分递归解决,难点在于第三部分。预处理后半段的两个数组,pre数组表示前缀数组的最大值(pre数组一定是单调不下降的),sum数组是pre数组前缀和。然后用双指针,前半段从后往前,维护最大值,后半段从前往后。