LintCode 402: Continuous Subarray Sum

題目描述

給定一個整數(shù)數(shù)組，請找出一個連續(xù)子數(shù)組，使得該子數(shù)組的和最大。輸出答案時，請分別返回第一個數(shù)字和最后一個數(shù)字的下標(biāo)。（如果兩個相同的答案，請返回其中任意一個）

樣例

給定[-3, 1, 3, -3, 4], 返回[1,4].

Thu Feb 23 2017

思路

本題有很多解法，最巧妙的解法就是一遍掃描記憶的方法了，時間復(fù)雜度為\(O(n)\)。

用一個變量記錄連續(xù)累加的和，當(dāng)和為負(fù)數(shù)時，變量清零，從下一個數(shù)字開始累加記錄。

在這里只需要注意一下一些小細(xì)節(jié)，比如如何記錄最大子數(shù)組的起始位置，以及處理一下數(shù)組中所有的數(shù)都是負(fù)數(shù)的情況。

代碼

// 連續(xù)子數(shù)組求和 vector<int> continuousSubarraySum(vector<int>& A) { int max_sum = -1, sum = 0, start;int is_all_negative = 1, max_num = -9e5, max_num_ind = -1vector<int> ans(2);for (int i = 0; i < A.size(); ++i){if (sum <= 0) start = i;sum += A[i];if (sum < 0) sum = 0;else if (sum > max_sum){is_all_negative = 0;max_sum = sum;ans[0] = start;ans[1] = i;}if (max_num < A[i]){max_num = A[i];max_num_ind = i;}}if (is_all_negative){ans[0] = ans[1] = max_num_ind;}return ans; }

轉(zhuǎn)載于:https://www.cnblogs.com/genkun/p/6435196.html

總結(jié)

以上是生活随笔為你收集整理的LintCode 402: Continuous Subarray Sum的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。