链接：LintCode 炼码 - ChatGPT！更高效的学习体验！
题解：
九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧
九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧
class Solution {
public:/*** @param a: An integer array* @return: A list of integers includes the index of the first number and the index of the last number*/vector<int> continuousSubarraySum(vector<int> &a) {// write your code hereif (a.size() <= 0) {return {};}std::vector<int> result;// 到达下标i的位置，最大的连续子数组和std::vector<int> dp(a.size(), 0);int max_res = a[0];// 最大连续子数组和的最后一个位置int max_pos = 0;dp[0] = a[0];// 记录之前的位置std::vector<int> dist(a.size(), 0);for (int i = 1; i < a.size(); ++i) {// 最长的位置就是自己dist[i] = i;// 最长的位置的前一个是由i-1得来的位置// 因为是求连续子数组和，所以dp[i]，可以由前一个位置+当前位置，或者是当前位置if (dp[i-1] + a[i] >= a[i]) {dist[i] = i-1;}dp[i] = max(dp[i-1] + a[i], a[i]);// 打擂台和结果进行比较if (dp[i] > max_res) {max_res = dp[i];max_pos = i;}}/*int sum = 0;int i = max_pos;for (; i >= 0; --i) {sum += a[i];if (sum == max_res) {break;}}*/// 求得起始位置int pos = max_pos;while (dist[pos] != pos) {pos = dist[pos];}result.push_back(pos);result.push_back(max_pos);return result;}
}; 
