大湮灭术

题目说明

世间充斥看正负两种能量，正能量对人体有益，而负能量对人体是有害的。已知地图上有n个排应一列的地域，每个地域的能量都不一样，可以用一个数字来代表某个地域中正负能量的数，正数代表正能量比负能量多，反之亦然。

现在大漫灭术的卷轴只剩下了两个，你可以对任何一个连续的区域使用大湮灭术，使用之后，无论该连续区域中能量有多少，都会清0。你希望天地间的正能量最多，请问船使得正能量最多为多少。(如果天地间都是正能量，不使用卷轴也是可以的)

解题思路

首先要明确一个问题，此处需要求的一个是区间的最大负能量，如果只是通过动态规划纯粹的从左向右遍历的话，得到的只是包含该位置在内的左边区间的最大负能量dp_left[]。因此为了解决这个问题，还需要从右向左再遍历一次dp_right[]，分别获得基于该位置的左右区间最大负能量后，相加再减掉一份当前位置的值后（计算左右区间都用了nums[i]）,便获得了区间最大负能量dp[]，遍历获得区间最小值first。在获取到first之后通过判定其是否小于0来决定是否需要使用大湮灭术（将这部分区间清零），还是直接返回结果结束。

然后通过暴力方法（暂时没有想到更好的定位方法）来确定是哪一段区间的和等于first值，当tmp == first时跳出循环。将这一段的数值置0，至此第一遍大湮灭术使用。

第二次使用大湮灭术的基本流程和第一次的流程基本相同，同样要经历通过获取左右区间最大负能量，获取区间最大负能量，决定是否使用大湮灭术这几个步骤。如果是k次使用大湮灭术的话，可以将其用函数写出来，可以减少代码的复杂程度，提高可读性、复用性并便于维护debug。

具体代码

package Test;

import java.util.*;

public class test {

    public static void main(String[] args) {
        // 假定以这个数组为例代表能力
        int[] nums = {-2, -2, -2, 1, -2, 3, 3, 3, 3, -2, -2, 1, -2, 3, 4};

        // 通过dp寻找左区间最大负能量
        int[] dp_left = new int[nums.length];
        // 左区间dp初始化
        dp_left[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp_left[i] = Math.min(nums[i], dp_left[i - 1] + nums[i]);
        }
        
        // 通过dp寻找右区间最大负能量
        int[] dp_right = new int[nums.length];
        // 右区间dp初始化
        dp_right[dp_right.length - 1] = nums[dp_right.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            dp_right[i] = Math.min(nums[i], dp_right[i + 1] + nums[i]);
        }

        // 左右子区间相加获得该位置最小子区间，记得减去一次当前nums[i]
        int[] dp = new int[nums.length];
        int first = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            dp[i] = dp_left[i] + dp_right[i] - nums[i];
            first = Math.min(first, dp[i]);
            System.out.printf(dp[i] + " ");
        }
        System.out.println();
        
        // 不需要使用湮灭术直接结束
        if(first > 0) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            System.out.println(sum);
            return;
        }

        // 大湮灭术，通过暴力的手段定位区间后把区间内能力清零
        int start = 0;
        int end = 0;
        int tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                tmp = 0;
                for (int t = i; t <= j; t++) {
                    tmp += nums[t];
                }
                if (tmp == first) {
                    start = i;
                    end = j;
                    break;
                }
            }
            if (tmp == first) {
                break;
            }
        }

        for (int i = start; i <= end; i++) {
            nums[i] = 0;
        }

        // 第二次使用湮灭术之前要将之前的变量重置
        Arrays.fill(dp_left, 0);
        int second = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            dp_left[i] = Math.min(nums[i], dp_left[i - 1] + nums[i]);
        }

        Arrays.fill(dp_right, 0);
        dp_right[dp_right.length - 1] = nums[dp_right.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            dp_right[i] = Math.min(nums[i], dp_right[i + 1] + nums[i]);
        }


        for (int i = 0; i < nums.length; i++) {
            dp[i] = dp_left[i] + dp_right[i] - nums[i];
            second = Math.min(second, dp[i]);
            System.out.printf(dp[i] + " ");
        }
        System.out.println();

        // 判定是否需要使用第二次大湮灭术
        if (second > 0) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            System.out.println(sum);
            return;
        }

        start = 0;
        end = 0;
        tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                tmp = 0;
                for (int t = i; t <= j; t++) {
                    tmp += nums[t];
                }
                if (tmp == second) {
                    start = i;
                    end = j;
                    break;
                }
            }
            if (tmp == second) {
                break;
            }
        }

        for (int i = start; i <= end; i++) {
            nums[i] = 0;
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        System.out.println(sum);
        return;


    }

}

（这段代码也无从验证是不是对的了，只能说自己搞了几个样例验证了一下好像也没问题，过程有将区间最小和的dp数组打印出来）