Subarray Sum Closest to Target
Given an array of N integers and a target integer T, find a subarray whose sum is as close as possible to T. A subarray is a contiguous part of the array. You need to output the absolute difference between the closest subarray sum and T. If there are multiple subarrays with the same minimum difference, any one is acceptable.
Input
The first line contains two integers N and T, separated by a space. The second line contains N space-separated integers, the elements of the array.
Output
Print a single integer, the minimum absolute difference between any subarray sum and T.
Constraints
1 <= N <= 200000, -10^9 <= T <= 10^9, -10^9 <= arr[i] <= 10^9
Example 1
5 10 3 7 2 5 8
0
Subarray [3, 7] sums to 10. Difference is |10-10| = 0.
Example 2
3 5 1 2 3
0
Subarray sums: 1, 2, 3, 1+2=3, 2+3=5, 1+2+3=6. Closest to 5 is 5 (diff 0) or 6 (diff 1) or 3 (diff 2). Minimum difference is 0 for subarray [2, 3].
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 10 3 7 2 5 8
3 5 1 2 3