链接LintCode 炼码 - ChatGPT更高效的学习体验题解九章算法 - 帮助更多程序员找到好工作硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧九章算法 - 帮助更多程序员找到好工作硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧1.维护一个前缀最小和和前缀最小和的末尾下标 min_prefix_sum和min_prefix_index2.同时记录整体前缀和sum-min_prefix_sum result 更新结果3.最小前缀和需要用sum来更新min_prefix_sum和min_prefix_indexclass 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 */ vectorint continuousSubarraySum(vectorint a) { // write your code here int len a.size(); if (len 0) { return {}; } vectorint 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; vectorint 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 */ vectorint continuousSubarraySum(vectorint a) { // write your code here if (a.size() 0) { return {}; } std::vectorint result; // 到达下标i的位置最大的连续子数组和 std::vectorint dp(a.size(), 0); int max_res a[0]; // 最大连续子数组和的最后一个位置 int max_pos 0; dp[0] a[0]; // 记录之前的位置 std::vectorint 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 ArrayListInteger continuousSubarraySum(int[] A) { ArrayListInteger result new ArrayListInteger(); 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 */ vectorint continuousSubarraySum(vectorint a) { // write your code here std::vectorint 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; } };