久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

# Continuous Subarray Sum II ### Source - lintcode: [(403) Continuous Subarray Sum II](http://www.lintcode.com/en/problem/continuous-subarray-sum-ii/) - [Maximum circular subarray sum - GeeksforGeeks](http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/) ### Problem Given an integer array, find a continuous rotate subarray where the sum ofnumbers is the biggest. Your code should return the index of the first numberand the index of the last number. (If their are duplicate answer, returnanyone. The answer can be rorate array or non- rorate array) #### Example Give `[3, 1, -100, -3, 4]`, return `[4,1]`. ### 題解 題 [Continuous Subarray Sum](http://algorithm.yuanbin.me/zh-cn/problem_misc/continuous_subarray_sum.html) 的 follow up, 這道題 AC 率極低，真是磨人的小妖精。在上題的基礎(chǔ)上容易想到可以將`first`和`last`分四種情況討論，然后再逆向求大于0的最大和即可，但是這種想法忽略了一種情況——旋轉(zhuǎn)后的最大值可能由兩段子數(shù)組和構(gòu)成，而這種情況如果用上題的解法則會被忽略。 所以這道題的正確解法不是分`first`和`last`四種情況討論，而是利用旋轉(zhuǎn)數(shù)組的特性。第一種情況，無論怎么拼接原數(shù)組中的數(shù)組和都無法大于最大的單一數(shù)組和；第二種情況則相反。所以現(xiàn)在問題的關(guān)鍵則轉(zhuǎn)化為怎么求第二種情況。首先可以明確一點，最終得到的數(shù)組和索引必須連續(xù)（含首尾相接）。也就是說情況二一旦出現(xiàn)，則我們可以將原數(shù)組中挖空一小段，現(xiàn)在問題來了：到底要挖掉多少元素？ **我們的目標(biāo)是使得挖掉后的元素值最大。**由于分段求解不容易（被隔開），但是被挖掉的元素索引是挨著的！正難則反！由于數(shù)組的總和是一定的，那么我們只要求得被挖掉部分元素的最小值即可得兩邊子數(shù)組的最大值！最后判斷兩個最大值孰大孰小就可以了。 ### Java ~~~ 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> continuousSubarraySumII(int[] A) { ArrayList<Integer> result = new ArrayList<Integer>(); if (A == null || A.length == 0) return result; // maximal subarray sum ArrayList<Integer> sub1 = subSum(A, 1); // minimal subarray sum ArrayList<Integer> sub2 = subSum(A, -1); int first = 0, last = 0; if (sub1.get(3) - sub2.get(2) > sub1.get(2)) { last = sub2.get(0) - 1; first = sub2.get(1) + 1; } else { first = sub1.get(0); last = sub1.get(1); } // corner case(all elements are negtive) if (last == -1 && first == A.length) { first = sub1.get(0); last = sub1.get(1); } result.add(first); result.add(last); return result; } private ArrayList<Integer> subSum(int[] A, int sign) { ArrayList<Integer> result = new ArrayList<Integer>(); // find the max/min subarray sum from [0...A.length] int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE; if (sign == -1) maxSub = Integer.MAX_VALUE; int first = 0, last = 0; int first2 = 0; // candidate for first for (int i = 0; i < A.length; i++) { if (sign * minSum > sign * sum) { minSum = sum; first2 = i; } sum += A[i]; if (sign * (sum - minSum) > sign * maxSub) { maxSub = sum - minSum; last = i; // update first if valid if (first2 <= last) first = first2; } } result.add(first); result.add(last); result.add(maxSub); result.add(sum); return result; } } ~~~ ### 源碼分析 由于既需要求最大子數(shù)組和，也需要求最小子數(shù)組和，我們將這一部分寫成一私有方法，并加入`sign`控制符號。如果兩段子數(shù)組和大于一段子數(shù)組和時，新的`first`和`last`正好相反。且在數(shù)組全為負(fù)時需要排除，直接使用單一子數(shù)組和最大的情況。 ### 復(fù)雜度分析 遍歷兩次數(shù)組，時間復(fù)雜度 O(n)O(n)O(n), 使用了部分額外 List, 空間復(fù)雜度 O(1)O(1)O(1). ### Reference - [CC150+Leetcode Continuous Subarray Sum II](http://meetqun.com/thread-9856-1-1.html)