获取利润第K大的值(Java /Py/C/C/Js/Go)题解华为OD机试真题 新系统 华为OD上机考试真题新系统 11月1号 100分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容小张是一名金融交易员现在记录了某只股票连续n个交易日每天的“涨跌金额”上涨为正、下跌为负、横盘为0)如果某次交易是“在某个交易日买入、之后某个交易日卖出”那么这笔交易的利润就等于这两点之间所有日子的涨跌金额之和。小张正在设计一个交易策略想找出所有可行交易时段里利润排名第K大的那个利润值以此观察收益分布。请你设计一个程序帮小张求出这个第K大的交易利润值。注意一次交易为买入日i→卖出日j(0ijn-1)”利润 a[i] a[i1] … a[i]只要买入日/卖出日不同就视为不同交易时段利润相同的不同时段也分别计入排名并列依次占用排名数组可包含负数因此利润可正、可负、可为0均按排名取第 K大的值输入描述第一行整型数组每个元素为当日涨跌金额可为负长度1 n 1000;第二行k正整数值范围1Kn*(n1)/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题解思路前缀和 枚举核心思路枚举每一个连续子数组计算区间和保存到数组中最后从大到小进行排序取第k个值即可。计算每个子数组区间和可通过前缀和进行加速sum(i, j) prefix[j 1] - prefix[i]注意区间和可能超过int的数据范围造成溢出应使用数据范围的数据类型进行处理。C#includebits/stdc.h#includevectorusingnamespacestd;usinglllonglong;// 通用 切割函数 函数 将字符串str根据delimiter进行切割vectorintsplit(conststringstr,conststringdelimiter){vectorintresult;size_t start0;size_t endstr.find(delimiter);while(end!string::npos){result.push_back(stoi(str.substr(start,end-start)));startenddelimiter.length();endstr.find(delimiter,start);}// 添加最后一个部分result.push_back(stoi(str.substr(start)));returnresult;}longlongsolve(vectorinta,intk){intna.size();// 计算前缀和vectorllpre(n1,0);for(inti0;in;i){pre[i1]pre[i]a[i];}// 枚举所有连续子数组和vectorllsums;for(inti0;in;i){for(intji;jn;j){sums.push_back(pre[j1]-pre[i]);}}// 从大到小排序sort(sums.begin(),sums.end(),greaterll());returnsums[k-1];}intmain(){string line;getline(cin,line);vectorintasplit(line, );intk;cink;coutsolve(a,k);return0;}Javaimportjava.util.*;publicclassMain{// 计算第 k 大的连续子数组和staticlongsolve(int[]a,intk){intna.length;// 计算前缀和long[]prenewlong[n1];for(inti0;in;i){pre[i1]pre[i]a[i];}// 枚举所有连续子数组和ListLongsumsnewArrayList();for(inti0;in;i){for(intji;jn;j){sums.add(pre[j1]-pre[i]);}}// 从大到小排序sums.sort(Collections.reverseOrder());returnsums.get(k-1);}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringlinesc.nextLine();String[]partsline.trim().split(\\s);int[]anewint[parts.length];for(inti0;iparts.length;i){a[i]Integer.parseInt(parts[i]);}intksc.nextInt();System.out.println(solve(a,k));sc.close();}}Python# 计算第 k 大的连续子数组和defsolve(a,k):nlen(a)# 计算前缀和pre[0]*(n1)foriinrange(n):pre[i1]pre[i]a[i]# 枚举所有连续子数组和sums[]foriinrange(n):forjinrange(i,n):sums.append(pre[j1]-pre[i])# 从大到小排序sums.sort(reverseTrue)returnsums[k-1]if__name____main__:alist(map(int,input().split()))kint(input())print(solve(a,k))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letlines[];rl.on(line,(line){lines.push(line.trim());});rl.on(close,(){constalines[0].split(/\s/).map(Number);constkNumber(lines[1]);console.log(solve(a,k));});// 计算第 k 大的连续子数组和functionsolve(a,k){constna.length;// 计算前缀和constprenewArray(n1).fill(0);for(leti0;in;i){pre[i1]pre[i]a[i];}// 枚举所有连续子数组和constsums[];for(leti0;in;i){for(letji;jn;j){sums.push(pre[j1]-pre[i]);}}// 从大到小排序sums.sort((a,b)b-a);returnsums[k-1];}Gopackagemainimport(bufiofmtossortstrconvstrings)// 计算第 k 大的连续子数组和funcsolve(a[]int,kint)int64{n:len(a)// 计算前缀和pre:make([]int64,n1)fori:0;in;i{pre[i1]pre[i]int64(a[i])}// 枚举所有连续子数组和sums:make([]int64,0)fori:0;in;i{forj:i;jn;j{sumsappend(sums,pre[j1]-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语言#includestdio.h#includestdlib.h#includestring.htypedeflonglongll;// 从大到小排序intcmp(constvoid*a,constvoid*b){ll x*(constll*)a;ll y*(constll*)b;if(xy)return-1;if(xy)return1;return0;}// 计算第 k 大的连续子数组和llsolve(inta[],intn,intk){// 计算前缀和ll pre[1005]{0};for(inti0;in;i){pre[i1]pre[i]a[i];}// 枚举所有连续子数组和ll sums[501000];intcnt0;for(inti0;in;i){for(intji;jn;j){sums[cnt]pre[j1]-pre[i];}}// 从大到小排序qsort(sums,cnt,sizeof(ll),cmp);returnsums[k-1];}intmain(){charline[20000];inta[1005];intn0;intk;// 读取第一行数组fgets(line,sizeof(line),stdin);char*tokenstrtok(line, \t\r\n);while(token!NULL){a[n]atoi(token);tokenstrtok(NULL, \t\r\n);}// 读取 kscanf(%d,k);printf(%lld\n,solve(a,n,k));return0;}
