数据结构与算法——连续子数组最大和
一、暴力算法 $\mathcal{O}(n^3)$ 遍历数组的所有子数组集合,并对其求和,筛选出和的最大值 int maxSumOfSub1(int* array, int length){ int maxSum = 0; int startIndex = 0, endIndex = 0; for(int i = 0; i < length; i++){ for(int j = i; j < length; j++){ int sum = 0; for(int k = i; k <= j; k++) sum += array[k]; if(maxSum < sum){ maxSum = sum; startIndex = i; endIndex = j; } } } cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl; return maxSum; } 二、前缀和 $\mathcal{O}(n^2)$ 先把数组的前 i 项和求出来并将其保存到数组中,然后计算所有子数组集合的和,筛选其中最大的...