连续子段绝对值最小问题

您所在的位置:网站首页 最小的小子 连续子段绝对值最小问题

连续子段绝对值最小问题

#连续子段绝对值最小问题| 来源: 网络整理| 查看: 265

【座右铭】1. 想要成为行家,就必须尝试解决大量的问题;

                    2. 解决大量问题并不代表能解决所有问题,而是表示解决下一个问题的几率变大了

1. 现有一个数组,里面包含了正数和负数,取其中若干个连续的数,要求这些数的和的绝对值最小【问题来源于论坛】

第一部分:思路

1. 对数组A[1...N],做和运算S[1...N],其中S[1] = A[1]; S[2] = A[1]+A[2];...;S[N]=A[1]+A[2]+A[3]+...+A[N]

2. 对S[1...N]从小到大排序

3. 连续子段绝对值最小:Min{ |S[i]|,S[i+1]-S[i]} 1



【本文地址】


今日新闻


推荐新闻


    CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3