获取利润第K大的值(Java /Py/C/C++/Js/Go)题解

华为OD机试真题 新系统 华为OD上机考试真题新系统 11月1号 100分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

小张是一名金融交易员，现在记录了某只股票连续n个交易日每天的“涨跌金额”（上涨为正、下跌为负、横盘为0)；如果某次交易是“在某个交易日买入、之后某个交易日卖出”，那么这笔交易的利润就等于这两点之间所有日子的涨跌金额之和。
小张正在设计一个交易策略，想找出所有可行交易时段里，利润排名第K大的那个利润值，以此观察收益分布。
请你设计一个程序，帮小张求出这个第K大的交易利润值。

注意：

• 一次交易为"买入日i→卖出日j(0<=i<=j<=n-1)”，利润= a[i] + a[i+1] + … + a[i]

• 只要买入日/卖出日不同就视为不同交易时段；利润相同的不同时段也分别计入排名（并列依次占用排名）

• 数组可包含负数，因此利润可正、可负、可为0，均按排名取第 K大的值

输入描述

第一行整型数组：每个元素为当日涨跌金额，可为负，长度1 <= n<= 1000;

第二行k：正整数，值范围1<=K<=n*(n+1)/2，不超过可行交易总数

输出描述

整型数值，表示所有可行交易利润（即所有连续子数组和）中，按从大到小排序后第K大的那个利润值；

样例1

输入

3 -2 5 3

输出

3

说明

(0, 0): 收益3 (0, 1): 收益1 (0, 2): 收益6 (1, 1): 收益-2 (1, 2): 收益3 (2, 2): 收益5 可获得的收益：6 5 3 3 1 -2 第k大收益为3

题解

思路：前缀和 + 枚举

1. 核心思路：枚举每一个连续子数组，计算区间和，保存到数组中，最后从大到小进行排序，取第k个值即可。
2. 计算每个子数组区间和可通过前缀和进行加速，sum(i, j) = prefix[j + 1] - prefix[i]
3. 注意：区间和可能超过int的数据范围造成溢出，应使用数据范围的数据类型进行处理。

C++

#include<bits/stdc++.h>#include<vector>usingnamespacestd;usingll=longlong;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vector<int>split(conststring&str,conststring&delimiter){vector<int>result;size_t start=0;size_t end=str.find(delimiter);while(end!=string::npos){result.push_back(stoi(str.substr(start,end-start)));start=end+delimiter.length();end=str.find(delimiter,start);}// 添加最后一个部分result.push_back(stoi(str.substr(start)));returnresult;}longlongsolve(vector<int>&a,intk){intn=a.size();// 计算前缀和vector<ll>pre(n+1,0);for(inti=0;i<n;i++){pre[i+1]=pre[i]+a[i];}// 枚举所有连续子数组和vector<ll>sums;for(inti=0;i<n;i++){for(intj=i;j<n;j++){sums.push_back(pre[j+1]-pre[i]);}}// 从大到小排序sort(sums.begin(),sums.end(),greater<ll>());returnsums[k-1];}intmain(){string line;getline(cin,line);vector<int>a=split(line," ");intk;cin>>k;cout<<solve(a,k);return0;}

Java

importjava.util.*;publicclassMain{// 计算第 k 大的连续子数组和staticlongsolve(int[]a,intk){intn=a.length;// 计算前缀和long[]pre=newlong[n+1];for(inti=0;i<n;i++){pre[i+1]=pre[i]+a[i];}// 枚举所有连续子数组和List<Long>sums=newArrayList<>();for(inti=0;i<n;i++){for(intj=i;j<n;j++){sums.add(pre[j+1]-pre[i]);}}// 从大到小排序sums.sort(Collections.reverseOrder());returnsums.get(k-1);}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Stringline=sc.nextLine();String[]parts=line.trim().split("\\s+");int[]a=newint[parts.length];for(inti=0;i<parts.length;i++){a[i]=Integer.parseInt(parts[i]);}intk=sc.nextInt();System.out.println(solve(a,k));sc.close();}}

Python

# 计算第 k 大的连续子数组和defsolve(a,k):n=len(a)# 计算前缀和pre=[0]*(n+1)foriinrange(n):pre[i+1]=pre[i]+a[i]# 枚举所有连续子数组和sums=[]foriinrange(n):forjinrange(i,n):sums.append(pre[j+1]-pre[i])# 从大到小排序sums.sort(reverse=True)returnsums[k-1]if__name__=="__main__":a=list(map(int,input().split()))k=int(input())print(solve(a,k))

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',(line)=>{lines.push(line.trim());});rl.on('close',()=>{consta=lines[0].split(/\s+/).map(Number);constk=Number(lines[1]);console.log(solve(a,k));});// 计算第 k 大的连续子数组和functionsolve(a,k){constn=a.length;// 计算前缀和constpre=newArray(n+1).fill(0);for(leti=0;i<n;i++){pre[i+1]=pre[i]+a[i];}// 枚举所有连续子数组和constsums=[];for(leti=0;i<n;i++){for(letj=i;j<n;j++){sums.push(pre[j+1]-pre[i]);}}// 从大到小排序sums.sort((a,b)=>b-a);returnsums[k-1];}

Go

packagemainimport("bufio""fmt""os""sort""strconv""strings")// 计算第 k 大的连续子数组和funcsolve(a[]int,kint)int64{n:=len(a)// 计算前缀和pre:=make([]int64,n+1)fori:=0;i<n;i++{pre[i+1]=pre[i]+int64(a[i])}// 枚举所有连续子数组和sums:=make([]int64,0)fori:=0;i<n;i++{forj:=i;j<n;j++{sums=append(sums,pre[j+1]-pre[i])}}// 从大到小排序sort.Slice(sums,func(i,jint)bool{returnsums[i]>sums[j]})returnsums[k-1]}funcmain(){scanner:=bufio.NewScanner(os.Stdin)// 读取第一行数组scanner.Scan()parts:=strings.Fields(scanner.Text())a:=make([]int,len(parts))fori,s:=rangeparts{a[i],_=strconv.Atoi(s)}// 读取 kscanner.Scan()k,_:=strconv.Atoi(strings.TrimSpace(scanner.Text()))fmt.Println(solve(a,k))}

C语言

#include<stdio.h>#include<stdlib.h>#include<string.h>typedeflonglongll;// 从大到小排序intcmp(constvoid*a,constvoid*b){ll x=*(constll*)a;ll y=*(constll*)b;if(x>y)return-1;if(x<y)return1;return0;}// 计算第 k 大的连续子数组和llsolve(inta[],intn,intk){// 计算前缀和ll pre[1005]={0};for(inti=0;i<n;i++){pre[i+1]=pre[i]+a[i];}// 枚举所有连续子数组和ll sums[501000];intcnt=0;for(inti=0;i<n;i++){for(intj=i;j<n;j++){sums[cnt++]=pre[j+1]-pre[i];}}// 从大到小排序qsort(sums,cnt,sizeof(ll),cmp);returnsums[k-1];}intmain(){charline[20000];inta[1005];intn=0;intk;// 读取第一行数组fgets(line,sizeof(line),stdin);char*token=strtok(line," \t\r\n");while(token!=NULL){a[n++]=atoi(token);token=strtok(NULL," \t\r\n");}// 读取 kscanf("%d",&k);printf("%lld\n",solve(a,n,k));return0;}