单选题最大子段和问题描述为，在n个整数（包含负数）的数组A中，求元素之和最大的非空连续子数组，如数组A=（-2，11，4，13，-5，-2），其子数组B=（11，-4，13）具有最大子段和 20（11-4+13=20）。求解该问题时，可以将数组分为两个n/2个整数的子数组最大子段和或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和，该算法的时间复杂度为（）。

A、 O(nlgn)
B、 O(n^2)
C、 O(n^2lgn)
D、 O(n^3)

【正确答案】 A

【答案解析】根据题干描述“求解该问题时，可以将数组分为两个n/2个整数的子数组最大子段和或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和”。可知采用的是分治法求解，时间复杂度为O(nlgn) 。