Trading System
Time limit1sMemory limit512 MB
Given n integers and k, list the k largest sums among all contiguous subarrays, in non-increasing order.
- Level
Hard8 of 10
- Topics
- Heap, Prefix sum, Binary search, Array
- Solved
- No attempts yet
Problem
SY Company wants to improve its stock trading system. For this, the company decides to use information on the fluctuation of stock prices. The fluctuation value is the difference in stock prices for two consecutive days. The company collects n recent fluctuation values for some stock. It turns out that the stock volatility is greatly affected by the largest sum of the contiguous fluctuation values. Finding such contiguous fluctuation values whose sum is the maximum is known as the largest sum contiguous subarray problem in computer science, where input values are stored in an array. It is natural that utilizing the k(≥ 1) largest contiguous sums rather than the largest one will help improve the trading system.
Write a program to find the k largest sums of contiguous fluctuation values for the given n fluctuation values and a positive integer k.
Input
Your program is to read from standard input. The input starts with a line containing two integers, n and k, where 1 ≤ n ≤ 250,000 and 1 ≤ k ≤ min(10,000, n(n + 1)/2). The next line contains n integers representing n fluctuation values. All fluctuation values are between −109 and 109 inclusively.
Output
Your program is to write to standard output. Print exactly one line. The line should contain the k largest sums of contiguous fluctuation values in non-increasing order. Note that any contiguous sum is the sum of one or more consecutive fluctuation values.