连续子段指的是序列中一段连续的数字。子段数字和指的是子段中所有数字相加的和。
5,2,[-4,4,-2,1,-3]
9
因为要选的子段的长度必须大于等于2,所以最优的选择是选择[4,-2,1],得到的答案为3
第一个参数n代表序列中的数字个数
第二个参数代表连续子段的长度要大于等于
第三个参数a包含个元素,代表给出的序列
class Solution { public: /** * k长连续子段和 * @param n int整型 * @param k int整型 * @param a int整型vector * @return long长整型 */ long long solve(int n, int k, vector<int>& a) { // write code here typedef long long ll; vector<ll> sum(n+1,0); vector<ll> dp(n+1,0); //构造sum数组 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i-1]; //dp从k开始,若i<k,第i个数字显然不能作为结尾 dp[k]=sum[k]; ll result=dp[k]; for(int i=k+1;i<=n;i++){ dp[i]=max(dp[i-1]+a[i-1],sum[i]-sum[i-k]); result=max(result,dp[i]); } return result; } };
solve(n, k, a: Array<number>) { let dp = new Array(n + 1).fill(0); let sum = 0; //先初始化 for (let i = 1; i <= k; i++) { dp[i] = dp[i - 1] + a[i - 1]; } let result = dp[k]; for (let i = k + 1; i <= n; i++) { sum += a[i - k - 1]; if (sum < 0) { //舍弃掉前半段,只留k个元素 dp[i] = dp[i - 1] + a[i - 1] - sum; sum = 0; } else { dp[i] = dp[i - 1] + a[i - 1]; } result = Math.max(dp[i], result); } return result; }