【算法实战】每日一题：将某个序列中内的每个元素都设为相同的值的最短次数（差分数组解法，附概念理解以及实战操作）

题目

将某个序列中内的每个元素都设为相同的值的最短次数

1.差分数组（后面的减去前面的值存储的位置可以理解为中间）

差分数组用于处理序列中的区间更新和查询问题。它存储序列中相邻元素之间的差值，而不是直接存储每个元素的值

怎么对某一段区间的值增加X

利用差分数组的特性来实现对某个区间 [L, R] 内的每个元素增加一个值 X 的操作。

差分数组存储的是每个元素与其前一个元素之间的差值。

在区间的起始位置 L 处将差分数组增加 X，相当于将该区间后面的所有元素都增加了 X。

然后，在区间的结束位置 R+1 处将差分数组减去 X，以抵消掉对后续元素的影响。这样就实现了对整个区间内每个元素增加 X 的操作。

2. 解决方案思路

在差分数组中，可以执行两种操作：对于正数和负数构成的区间，可以对区间内的每个值增加或减少一个数来实现值相同；（本质上是一种相互抵消）

对于那些无法配对的正数或负数，可以考虑将当前位置与超出序列范围的位置进行操作，相当于是右边的区间内所有值都受到影响。

基于这个思路，我们可以通过统计序列中正数和负数的个数，通过第一种操作将它们抵消，然后通过第二种操作将剩余的正数或负数变成 0，从而实现所有值相同的目标。

在这个问题中，实际上是要求找到序列中正数或负数的最大值，以确定最少的调整次数，使得所有值相同。(注意这里不是正负数的个数，而是正负数里面的最大值)

3. 解决方案

.
def main():n = int(input())a=[]for i in range(n):a.append(int(input()))passsub = [0] * (n+1)num1 = 0num2 = 0for i in range(1,n):sub[i] = a[i] - a[i - 1]if sub[i] > 0:num1 += sub[i] else:num2 += sub[i]print(max(num1, -num2))if __name__ == '__main__':main()

END