The maximum subarray sum problem is to find the subarray with the maximum sum. For example, given an array {12, −13, −5, 25, −20, 20, 30}, the maximum subarray sum is 55. The time complexity to compute the maximum subarray sum with n element is/are ____.
1
O(n)
2
θ (n2)
3
Ω (n3)
4
O(nlog(n))