Since the sumRange will be called many times
We should think a way that to reuse the sums
This apprach only travers the array once and store sum of 0th to n-th
Input [-2, 0, 3, -5, 2, -1]
Record [-2, -2, 1, -4, -2, -3]
sumRange(i,j) = sum[j] - sum[i - 1]
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q303RangeSumQuery.playground/Contents.swift
No comments:
Post a Comment