← 返回 amazon 的题目列表PreSum Based Coding Problem
类型：online_judge
Given an integer array, design an algorithm to calculate the sum of a subarray where a particular value of the subarray is maximized. Implement a presum method where the input is an integer array and a target integer value. Aim for time complexity as close to O(n) as possible.
Input:
Integer array arr, indicating the given sequence.
Integer target, the target value we want the subarray sum to approach as closely as possible.
Output:
Integer, representing the sum of the subarray satisfying the condition.
Constraints:
1 <= len(arr) <= 10^5
-10^4 <= arr[i], target <= 10^4
Example:
Input: arr = [1, 2, 3, 4, 5], target = 10 Output: 10
Input: arr = [8, -2, 1, 7], target = 5 Output: 5
Example
Input
1
1 2 3 4 5
10