思路：动态规划
以下思路考场能AC，但是有点问题。
定义dp[i][j][0]代表a[i,...,j]中连续子段的最小值
定义dp[i][j][1]代表a[i,...,j]中连续子段的最大值
可以采用二维循环求出dp数组。
P1899.第3题-玩游戏
小乖和小坏在玩一个游戏，游戏中有一个长度为 n 的数组a1,a2,...,an 和一个固定的整数k。游戏规则如下，双方都会执行最优策略:
第一步,小乖选择一个非空的区间 [l,r]，将这个区间中的所有数字都乘上 k。
第二步, 小坏选择一个非空的区间 [l,r], 将这个区间中的所有数字都乘上 k。
记sum=i=1∑nai 小坏想让sum尽可能小，小乖想让sum尽可能大，你需要求出最后 sum 的值。
输入描述
第一行输入两个整数 n 和 k(10−5≤k≤105,1≤n≤1000;−105≤ai≤105),代表数组长度和固定的整数。
第二行输入 n 个整数 a1,a2,...,an, (−105≤ai≤105)代表数组。
输出描述
在一行上输出一个整数表示答案。
示例 1
输入
6 2
-1 -2 -3 1 2 3
输出
0
说明
小乖会选择区间[4,6],数组变成{−1,−2,−3,2,4,6}；
小坏会选择区间[1,3],数组变成{−2,−4,−6,2,4,6}；
数组总和为 0。
