c++ MaxDoubleSliceSum编码算法

ovfsdjhp  于 2023-07-01  发布在  其他
关注(0)|答案(5)|浏览(128)

我在Codility Lessons上偶然发现了这个问题，下面是描述：
给出一个由N个整数组成的非空零索引数组A。
一个三元组（X，Y，Z），使得0 ≤ X < Y < Z < N，称为双切片。
双切片（X，Y，Z）的和是A[X + 1] + A[X + 2] +…+ A[Y − 1] + A[Y + 1] + A[Y + 2] + ...+ A[Z − 1]。
例如，数组A使得：

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

包含以下双切片示例：
双切片（0，3，6），和为2 + 6 + 4 + 5 = 17，
double slice（0，3，7），sum = 2 + 6 + 4 + 5 − 1 = 16，
double slice（3，4，5），sum为0。
目标是找到任何双切片的最大和。
写一个函数：
int solution（vector &A）;
给定由N个整数组成的非空零索引数组A，返回任何双切片的最大和。
例如，给定：

A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2

函数应该返回17，因为数组A的双切片的和都不大于17。
假设：
N是在[3..100，000]范围内的整数;数组A的每个元素都是[-10，000..10，000]范围内的整数。
复杂度：
时间复杂度为O（N）;最坏情况下的空间复杂度是O（N），超出输入存储（不计算>输入参数所需的存储）。
可以修改输入数组的元素。
我已经读过关于计算MaxSum从索引i开始到索引i结束的算法，但我不知道为什么我的方法有时会产生不好的结果。这个想法是计算在索引i结束的MaxSum，省略范围0..i的最小值。下面是我的代码：

int solution(vector<int> &A) {
    int n = A.size();

    int end = 2;   

    int ret = 0;
    int sum = 0;

    int min = A[1];

    while (end < n-1)
    {
        if (A[end] < min)
        {
            sum = max(0, sum + min);
            ret = max(ret, sum);
            min = A[end];
            ++end;
            continue;
        }
        sum = max(0, sum + A[end]);
        ret = max(ret, sum);
        ++end;
    }

    return ret;
}

如果你能帮我指出漏洞，我会很高兴的！

c++

5条答案

按热度按时间
hrirmatl

hrirmatl1#

我的解决方案基于双向Kadane算法。更多详情请访问我的博客here。满分100分。

public int solution(int[] A) {
  int N = A.length;
  int[] K1 = new int[N];
  int[] K2 = new int[N];

  for(int i = 1; i < N-1; i++){
    K1[i] = Math.max(K1[i-1] + A[i], 0);
  }
  for(int i = N-2; i > 0; i--){
    K2[i] = Math.max(K2[i+1]+A[i], 0);
  }

  int max = 0;

  for(int i = 1; i < N-1; i++){
    max = Math.max(max, K1[i-1]+K2[i+1]);
  }

  return max;
}
赞(0）分享  回复(0）举报  2023-07-01
o8x7eapl

o8x7eapl2#

下面是我的代码：

int get_max_sum(const vector<int>& a) {
    int n = a.size();
    vector<int> best_pref(n);
    vector<int> best_suf(n);
    //Compute the best sum among all x values assuming that y = i.
    int min_pref = 0;
    int cur_pref = 0;
    for (int i = 1; i < n - 1; i++) {
        best_pref[i] = max(0, cur_pref - min_pref);
        cur_pref += a[i];
        min_pref = min(min_pref, cur_pref);
    }
    //Compute the best sum among all z values assuming that y = i.
    int min_suf = 0;
    int cur_suf = 0;
    for (int i = n - 2; i > 0; i--) {
        best_suf[i] = max(0, cur_suf - min_suf);
        cur_suf += a[i];
        min_suf = min(min_suf, cur_suf);
    }
    //Check all y values(y = i) and return the answer.
    int res = 0;
    for (int i = 1; i < n - 1; i++)
        res = max(res, best_pref[i] + best_suf[i]);
    return res;
 }

 int get_max_sum_dummy(const vector<int>& a) {
    //Try all possible values of x, y and z.
    int res = 0;
    int n = a.size();
    for (int x = 0; x < n; x++)
        for (int y = x + 1; y < n; y++)
            for (int z = y + 1; z < n; z++) {
                int cur = 0;
                for (int i = x + 1; i < z; i++)
                    if (i != y)
                        cur += a[i];
                res = max(res, cur);
            }
    return res;
 }

bool test() {
    //Generate a lot of small test cases and compare the output of 
    //a brute force and the actual solution.
    bool ok = true;
    for (int test = 0; test < 10000; test++) {
        int size = rand() % 20 + 3;
        vector<int> a(size);
        for (int i = 0; i < size; i++)
            a[i] = rand() % 20 - 10;
        if (get_max_sum(a) != get_max_sum_dummy(a))
            ok = false;
    }
    for (int test = 0; test < 10000; test++) {
        int size = rand() % 20 + 3;
        vector<int> a(size);
        for (int i = 0; i < size; i++)
            a[i] = rand() % 20;
        if (get_max_sum(a) != get_max_sum_dummy(a))
            ok = false;
    }
    return ok;
}

实际的解决方案是get_max_sum函数（另外两个是蛮力解决方案和测试器函数，用于生成随机数组并比较蛮力和实际解决方案的输出，我仅将它们用于测试目的）。
我的解决方案背后的想法是计算一个子数组中的最大和，该子数组开始于i之前的某个地方，结束于i - 1，然后对足够数（分别为best_pref[i]和best_suf[i]）做同样的事情。之后，我只是迭代所有的i并返回best_pref[i] + best_suf[i]的最佳值。它正确工作，因为best_pref[y]为固定的y找到最好的x，best_suf[y]为固定的y找到最好的z，并且检查了y的所有可能值。

赞(0）分享  回复(0）举报  2023-07-01
ax6ht2ek

ax6ht2ek3#

def solution(A):
    n = len(A)
    K1 = [0] * n
    K2 = [0] * n
    for i in range(1,n-1,1):
        K1[i] = max(K1[i-1] + A[i], 0)

    for i in range(n-2,0,-1):
        K2[i] = max(K2[i+1]+A[i], 0)

    maximum = 0;
    for i in range(1,n-1,1):
        maximum = max(maximum, K1[i-1]+K2[i+1])

    return maximum

def main():
    A = [3,2,6,-1,4,5,-1,2]
    print(solution(A))

if __name__ == '__main__': main()
赞(0）分享  回复(0）举报  2023-07-01
uxhixvfz

uxhixvfz4#

Ruby100%

def solution(a)
  max_starting =(a.length - 2).downto(0).each.inject([[],0]) do |(acc,max), i|
    [acc, acc[i]= [0, a[i] + max].max ]
  end.first

  max_ending =1.upto(a.length - 3).each.inject([[],0]) do |(acc,max), i|
    [acc, acc[i]= [0, a[i] + max].max ]
  end.first

  max_ending.each_with_index.inject(0) do |acc, (el,i)|
    [acc, el.to_i + max_starting[i+2].to_i].max
  end
end
赞(0）分享  回复(0）举报  2023-07-01
hc2pp10m

hc2pp10m5#

Java：一种替代方法

import static java.lang.String.format;

public final class MaxDoubleSliceSum {

    private MaxDoubleSliceSum() {
        super();
    }

    private static int maxSumOfSlice(final int[] array) {
        if (array.length < 3) {
            throw new IllegalArgumentException("Length of array should be >=3");
        }
        final DoubleSlice firstSlice = DoubleSlice.firstSlice(array);
        DoubleSlice candidate = firstSlice;
        DoubleSlice max = firstSlice;
        for (int i = 1; i < array.length - 1 && candidate.couldBeExtended(); i++) {
            candidate = withMaxSum(candidate.extendRight(), candidate.nextShortest());
            max = withMaxSum(candidate, max);
        }
        max = max.fixLeftBoundary();
        return (int) max.sum;
    }

    private static DoubleSlice withMaxSum(final DoubleSlice thisSlice, final DoubleSlice thatSlice) {
        return thisSlice.sum >= thatSlice.sum ? thisSlice : thatSlice;
    }

    private static final class DoubleSlice {
        private final int[] array;
        private final int startExcl;
        private final int minExcl;
        private final int endExcl;
        private final long sum;

        private DoubleSlice(final int[] array, final int startExcl, final int minExcl, final int endExcl, final long sum) {
            this.array = array;
            this.startExcl = startExcl;
            this.minExcl = minExcl;
            this.endExcl = endExcl;
            this.sum = sum;
        }

        static DoubleSlice firstSlice(final int[] array) {
            return new DoubleSlice(array, 0, 1, 2, 0);
        }

        DoubleSlice extendRight() {
            // When the min element to exclude form total sum calculation wasn't changed,
            // adding the value of element at position this.endExcl to sum
            if (array[minExcl] <= array[this.endExcl]) {
                return new DoubleSlice(array, startExcl, minExcl, this.endExcl + 1, sum + array[this.endExcl]);
            }
            // When the min element to exclude form total sum calculation was changed
            // adding the value of previous min element to sum
            return new DoubleSlice(array, startExcl, this.endExcl, this.endExcl + 1, sum + array[this.minExcl]);
        }

        DoubleSlice nextShortest() {
            return new DoubleSlice(array, endExcl - 1, endExcl, endExcl + 1, 0);
        }

        DoubleSlice fixLeftBoundary() {
            // Check if there is a chance to maximize the sum by moving left boundary to right with 1 position
            if (array[startExcl + 1] >= 0) {
                return this;
            }
            // Check if we have place to move left boundary, the max distance from start to end is 2 (start,middle,end)
            if (startExcl == endExcl - 2) {
                return this;
            }
            int minIdx = startExcl + 2;
            for (int i = startExcl + 3; i < endExcl; i++) {
                if (array[i] < array[minIdx]) {
                    minIdx = i;
                }
            }
            // No negative element was found after element at position startExcl + 1, total sum couldn't be reduced
            if (array[minIdx] >= 0) {
                return this;
            }
            // Excluding from total sum calculation the value of element at position at minIdx,
            // the element at startExcl + 1 position was already was excluded from total sum calculation
            if (startExcl + 1 == minExcl) {
                return new DoubleSlice(array, startExcl + 1, minIdx, endExcl, sum - array[minIdx]);
            }
            // Excluding from total sum calculation the value of element at position at startExcl + 1
            return new DoubleSlice(array, startExcl + 1, minIdx, endExcl, sum - array[startExcl + 1]);
        }

        public boolean couldBeExtended() {
            return endExcl < array.length - 1;
        }

    }

    private static int[] intArray(int... array) {
        return array;
    }

    private static void assertCorrectMaxSumOfSlice(final int[] array, final int expected) {
        final var calculated = maxSumOfSlice(array);
        if (calculated != expected) {
            throw new AssertionError(format("expected '%d' - calculated '%d'", expected, calculated));
        }
    }

    public static void main(String[] args) {
        assertCorrectMaxSumOfSlice(
                intArray(
                        -1, -1, -1, -1, -1, -1
                ),
                0
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        3, 2, 6, -1, 4, 5, -1, 2
                ),
                17
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        0, 10, -5, -2, 0
                ),
                10
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        -8, 10, 20, -5, -7, -4),
                30
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        1, 7, 8, 2, -3, 4
                ),
                17
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        1, -9, -9, 2, 4, 5, 8, -1, -1, 4
                ),
                19
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        1, 3, 4, 2, -3, 4, -10, 1, 1, 4, -2, 4, 1),
                18
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        -8953, -8257, -1855, -7846, 8024, -9237, 724, -3356, 7042, -6807, -3256, -3324, -5097, -9967, -1275, -8248, 1952, -8603, -3691, -1034, 8108, -8145, -7157, 5802, -9576, 8223, 1468, -4694, 6757, 5376, -3131, 6030, -5863, 2178, 542, 6187, -3695, -2035, 5386, 255, 3697, 2767, 3333, 7802, -277, 3370, -2510, -9364, 5084, -6371, 6404, 8273, 3162, -6598, -3262, -2176, -8535, -865, 1463, -3278, -6219, -8237, 2566, -9744, -2962, -5418, 640, 4473, 8183, 2776
                ),
                57718);
        assertCorrectMaxSumOfSlice(
                intArray(
                        -4, -5, -1, -5, -7, -19, -11
                ),
                0
        );
        assertCorrectMaxSumOfSlice(
                intArray(
                        -27, -25, -6, -24, 24, -28, 2, -10, 21, -21, -10, -10, -16, -30, -4, -25, 6, -26, -11, -3, 25, -25, -22, 18, -29, 25, 4, -14, 21, 16, -10, 18, -18, 7, 2, 19, -11, -6, 16, 1, 11, 8, 10, 24, -1, 10, -8, -29, 16, -19, 20, 25, 10, -20, -10, -7, -26, -3, 4, -10, -19, -25, 8, -30, -9, -17, 2, 14, 25, 8, 30, 28, 8, -16, -1, -20, 30, -3, 15, -28, -22, -19, -15, -9, -14, -4, -5, -24, -27, -9, -25, -4, -30, 2, -26, 12, -6, 30, -14, -2, 15, -10, -9, 8, 29, 23, -5, 13, 11, -8, -16, -26, 23, -27, 1, 2, -22, 10, 25, 17, -7, -23, 29, 1, 8, 18, -7, -27, -22, 10, -9, 23, 15, 29, 10, -12, 18, -29, 1, 23, 1, -22, 0, 3, -8, 24, -10, -14, 0, -18, -11, -6, 27, -26, -18, -18, 30, 24, -19, 4, -25, -11, -10, 2, 26, 19, 2, 17, -1, 14, 17, -15, 20, 5, -1, -6, -17, 0, -23, 8, 24, 18, 7, 0, 12, -23, -27, 22, -8, 10, -5, -9, 16, -10, 15, 20, -19, 29, -27, -5, 0, 20, -20, 4, -8, 26, -23, -14, 20, -11, 27, -27, -7, -24, 4, 28, -11, 9, -14, -4, 4, -15, 12, 0, 25, -14, 28, -19, -29, 10, 14, -1, -28, 30, -22, 23, 24, -17, 22, -2, 24, 24, 17, -13, 5, 29, -11, -7, 11, -27, -15, -20, -5, -5, 7, 0, -20, -28, 2, 16, 26, 21, -12, 22, -2, -13, -25, -3, 3, -13, -19, 27, -26, 27, -6, 18, -24, 4, 16, -4, -9, 0, -19, -18, -16, -28, 25, -26, 26, -30, 10, 3, -28, 27, 14, 23, -4, -13, -19, -24
                ),
                262
        );
    }
}
赞(0）分享  回复(0）举报  2023-07-01
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com