arrays - 找出连续元素的最大可能差异之和

Question

Array A contains the elements, A1,A2...AN. And array B contains the elements, B1,B2...BN. There is a relationship between Ai and Bi, for 1 = i = N, i.e., any element Ai lies between 1 and Bi.

令数组 A 的成本 S 定义为:

你必须打印 S 的最大可能值。
问题的链接是 Problem

示例:
数组大小:5
数组:10 1 10 1 10
输出:36 (因为最大值可以导出为|10 - 1| + |1 - 10| + |10 - 1| + |1 - 10|)

方法:
我能想到的唯一方法是蛮力。我想我会做一个重叠的递归方程，这样我就可以记住它，但没能做到。

代码:

public static void func(int pos,int[] arr,int[] aux,int n)
    {
        /*
         * pos is current index in the arr
         * arr is array
         * aux is temp array which will store one possible combination.
         * n is size of the array.
         * */



        //if reached at the end, check the summation of differences
        if(pos == n)
        {
            long sum = 0;
            for(int i = 1 ; i < n ; i++)
            {
                //System.out.print("i = " + i + ", arr[i] = " + aux[i] + " ");
                sum += Math.abs(aux[i] - aux[i - 1]);
            }
            //System.out.println();
            //System.out.println("sum = " + sum);
            if(sum > max)
            {
                max = sum;
            }
            return;
        }

        //else try every combination possible.
        for(int i = 1 ; i <= arr[pos] ; i++)
        {
            aux[pos] = i;
            func(pos + 1,arr,aux,n);
        }
}

注意:
这个的复杂度是O(n*2^n)

Answer 1

首先，a[i] 没有理由应该等于 1 和 b[i] 之外的任何数字。意识到我们可以写下一个简单的循环:

fmax(1) = fone(1) = 0
fmax(i) = max(fone(i-1) + b[i] - 1, fmax(i-1) + abs(b[i]-b[i-1]))
fone(i) = max(fone(i-1), fmax(i-1) + b[i-1] - 1)

answer = max(fmax(N), fone(N)) 

其中 fmax(i) 是以 b[i] 结尾的 a[1..i] 元素的最大总和， fone(i) 是以 1 结尾的 a[1..i] 元素的最大总和。

使用动态规划方法，复杂度为O(N)。