小红书笔试真题 9.17 - 加速窗口收益(C++/Py/Java /Js/Go)

加速窗口收益

小红书 9月17号 笔试真题 第一题

题目内容

推理集群上排着 $m$ 项作业，第 $p$ 项有一个收益 $v_p$（正数表示划算，负数表示亏本）。
调度允许开一次加速窗口：挑一段连续作业 $[L,R]$（$1\le L\le R\le m$），把这段里每一项的收益改成原来的两倍。也可以一次都不开。
窗口用完之后（或者根本没用），再从作业序列里取出一段非空的连续作业，使它们的收益加起来尽量大。请给出这个最大和。
取出的那段至少要包含一项，不能交空段。

输入描述

首行给出正整数 $k$（$1\le k\le 2\times 10^1$），即询问组数。
随后 $k$ 行，每行先写出正整数 $m$（$1\le m\le 2\times 10^5$），再跟 $m$ 个整数 $v_1,v_2,\dots ,v_m$（$|v_p|\le 1000000000$），即该组作业条数和各项收益。
各组 $m$ 加起来不超过 $200000$。

输出描述

一行输出 $k$ 个整数，相邻两项用空格隔开，依次为每组询问的最大连续收益和。

样例1

输入

2
4 2 -3 4 -1
3 -5 -2 -7

输出

8 -2

说明

• 第一组：把 $[3,3]$（收益 $4$）翻倍，序列变成 $2,-3,8,-1$。最大连续和是单独的 $8$。
• 第二组：全是负数，翻倍只会更亏，不开窗口，答案是最大的一项 $-2$。

样例2

输入

1
6 1 2 -5 3 -1 4

输出

12

说明
把 $[4,6]$（$3,-1,4$）翻倍，这段和从 $6$ 变成 $12$。左侧 $1,2,-5$ 接上去会变差，所以最大就是 $12$。

题解和思路

思路

实现思路：动态规划

C++

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
vector<ll> res(k);
for (int x = 0; x < k; x++) {
int m;
cin >> m;
vector<ll>v(m);
for (int i = 0; i < m; i++) {
cin >> v[i];
}
ll ans = –1000000006;
ll last = 0;
for (int i = 0; i < m; i++) {
if (last > 0) {
last = last + v[i];
} else {
last = v[i];
}
ans = max(ans, last);
}
if (ans > 0) {
ans *= 2;
}
res[x] = ans;
}
for (int i = 0; i < k; i++) {
if (i > 0) {
cout << " ";
}
cout << res[i];
}
return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int k = sc.nextInt();
long[] res = new long[k];

for (int x = 0; x < k; x++) {
int m = sc.nextInt();

long[] v = new long[m];
for (int i = 0; i < m; i++) {
v[i] = sc.nextLong();
}

long ans = –1000000006L;
long last = 0;

for (int i = 0; i < m; i++) {
if (last > 0) {
last = last + v[i];
} else {
last = v[i];
}

ans = Math.max(ans, last);
}

if (ans > 0) {
ans *= 2;
}

res[x] = ans;
}

for (int i = 0; i < k; i++) {
if (i > 0) {
System.out.print(" ");
}
System.out.print(res[i]);
}
}
}

python

import sys

input = sys.stdin.readline

k = int(input())

res = [0] * k

for x in range(k):
data = list(map(int, input().split()))
m = data[0]
v = data[1:]
ans = –1000000006
last = 0

for i in range(m):
if last > 0:
last = last + v[i]
else:
last = v[i]

ans = max(ans, last)

if ans > 0:
ans *= 2

res[x] = ans

print(*res)

Javascript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

const input = [];

rl.on('line', (line) => {
input.push(line.trim());
});

rl.on('close', () => {
let idx = 0;

const k = Number(input[idx++]);
const res = new Array(k);

for (let x = 0; x < k; x++) {

const data = input[idx++].split(/\\s+/).map(Number);
const m = data[0];
const v = data.slice(1, m + 2);
let ans = –1000000006;
let last = 0;

for (let i = 0; i < m; i++) {
if (last > 0) {
last = last + v[i];
} else {
last = v[i];
}

ans = Math.max(ans, last);
}

if (ans > 0) {
ans *= 2;
}

res[x] = ans;
}

console.log(res.join(' '));
});

Go

package main

import (
"bufio"
"fmt"
"os"
)

func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()

var k int
fmt.Fscan(in, &k)

res := make([]int64, k)

for x := 0; x < k; x++ {
var m int
fmt.Fscan(in, &m)

v := make([]int64, m)
for i := 0; i < m; i++ {
fmt.Fscan(in, &v[i])
}

var ans int64 = –1000000006
var last int64 = 0

for i := 0; i < m; i++ {
if last > 0 {
last = last + v[i]
} else {
last = v[i]
}

if last > ans {
ans = last
}
}

if ans > 0 {
ans *= 2
}

res[x] = ans
}

for i := 0; i < k; i++ {
if i > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, res[i])
}
}