链接：LintCode 炼码 - ChatGPT！更高效的学习体验！

题解：

九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

1.维护一个前缀最小和，和前缀最小和的末尾下标 min_prefix_sum和min_prefix_index

2.同时记录整体前缀和，sum-min_prefix_sum > result 更新结果

3.最小前缀和需要用sum来更新min_prefix_sum和min_prefix_index

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 here int len = a.size(); if (len <= 0) { return {}; } vector<int> result_index; int sum = 0; int min_prefix_sum = 0; int min_prefix_index = -1; int result = INT_MIN; for (int i = 0; i < len; ++i) { sum += a[i]; if (sum - min_prefix_sum > result) { result = sum - min_prefix_sum; vector<int> tmp{min_prefix_index + 1, i}; result_index = move(tmp); } if (sum < min_prefix_sum) { min_prefix_sum = sum; min_prefix_index = i; } } return result_index; } };

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 here if (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; } };

public class Solution { /** * @param A an integer array * @return A list of integers includes the index of the first number and the index of the last number */ public ArrayList<Integer> continuousSubarraySum(int[] A) { ArrayList<Integer> result = new ArrayList<Integer>(); result.add(0); result.add(0); int len = A.length; int start = 0, end = 0; int sum = 0; int ans = -0x7fffffff; for (int i = 0; i < len; i++) { if (sum < 0) { sum = A[i]; start = end = i; } else { sum += A[i]; end = i; } if (sum > ans) { ans = sum; result.set(0, start); result.set(1, end); } } return result; } }

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 here std::vector<int> result; if (a.size() <= 0) { return result; } int sum = a[0]; int max_res = a[0]; result.push_back(0); result.push_back(0); int begin = 0; if (sum < 0) { sum = 0; begin = 1; } for (int i = 1; i < a.size(); ++i) { sum += a[i]; //cout << i << " " << sum << endl; if (sum > max_res) { //cout << "begin: " << begin << endl; result[0] = begin; result[1] = i; max_res = sum; } if (a[i] > max_res) { //cout << "begin: " << begin << endl; result[0] = i; result[1] = i; max_res = a[i]; } if (sum < 0) { //cout << "hahah: " << endl; begin = i + 1; sum = 0; } } return result; } };