算法|【算法】求一个数组中连续数字之和最大的值算法|java

题目：
求一个数组中连续数字之和最大值。其中连续数字可以从末尾到起始值，举例：
数组：1，-2，1，3，-1，3
最大值：7，数组是1，-2，1，3，-1，3
要求：
数组最大长度是100000
值符合[-2000,2000]
计算时间小于100ms
思考：
这个问题相当于：1）以第m个元素开始，以第m-1个元素结束，计算其最大值；2）然后遍历了第[1,n]个最大元素开始的数组后，取最大值。
算法复杂度为n*n
有一些优化点：
1、计算所有元素的值，只需要在计算第一个元素为起始点时即可
2、如果下一个值为非负数，那么可以忽略它作为下一个计算开始值。
单线程的算法实现
问题：在[1,-1,1,-1…]这种循环正负数的数组中，计算时间一直超过100ms

import java.util.ArrayList; import java.util.concurrent.*; public class ProfitInfo { public static final int MAX = 100000; public int[] mProfits = new int[MAX+1]; public int N; public ProfitInfo() {}public int getMaxProfits() { int answer = 0; answer = getProfitFromBeginToEnd(1, N); return answer; }private int getProfitFromBeginToEnd(int begin, int end) { int currentProfit = mProfits[begin]; int maxProfit = currentProfit; int[] currentResult = {0,0}; for (int i = begin; i <= end; i++) { currentResult = getMaxProfitByIndex(i ,begin, end); currentProfit = currentResult[0]; i = currentResult[1]; if(currentProfit > maxProfit) { maxProfit = currentProfit; } } return maxProfit; }private int[] getMaxProfitByIndex(int index, int begin, int end) { int currentProfits = mProfits[index]; int maxProfits = currentProfits; int[] result = {0,0}; int lastProfits = currentProfits; boolean isEnd = false; int currentProfit; int currentIndex; result[0] = currentProfits; result[1] = index; if (currentProfits > 0) { for (int len = 1; len < N; len++) { if (index != begin && len == (N-1)) { continue; } currentIndex = getIndex(index, len); currentProfit = mProfits[currentIndex]; currentProfits = lastProfits + currentProfit; lastProfits = currentProfits; if(currentProfits > maxProfits) { maxProfits = currentProfits; }if(currentProfit < 0 && !isEnd && currentIndex > index && currentIndex <= end) { result[1] = currentIndex; isEnd = true; } } if (!isEnd) { result[1] = end; } result[0] = maxProfits; } return result; }private int getIndex(int index, int length) { int tempIndex = index + length; if (tempIndex <= N) { return tempIndex; } else { return tempIndex - N; } } }

多线程的算法实现
问题：在[1,-1,1,-1…]这种循环正负数的数组中，计算时间比单线程算法好些，但是还是超过100ms

import java.util.ArrayList; import java.util.concurrent.*; public class ProfitInfo { public static final int MAX = 100000; public int[] mProfits = new int[MAX+1]; public int N; public ProfitInfo() {}public int getMaxProfits() { int answer = 0; final int NUMBER = 5000; if (N <= NUMBER) { answer = getProfitFromBeginToEnd(1, N); } else { ExecutorService exec = Executors.newCachedThreadPool(); ArrayList> results = new ArrayList>(); int num =0; if(N%NUMBER == 0) { num = N/NUMBER; } else { num = N/NUMBER + 1; } for (int i = 0; i < num; i++) { if (i <(num - 1)) { results.add(exec.submit(new TaskWithResult(1 + i * NUMBER, (i + 1) * NUMBER))); } else { results.add(exec.submit(new TaskWithResult(1 + i * NUMBER, N))); } } int tempAnswer = 0; boolean isFisrt = true; for(Future fs : results) { try { tempAnswer = fs.get(); if(isFisrt) { answer = tempAnswer; } else { if (tempAnswer > answer) { answer = tempAnswer; } } } catch (InterruptedException e) {} catch (ExecutionException e) {} finally { exec.shutdown(); } } }return answer; }private int getProfitFromBeginToEnd(int begin, int end) { int currentProfit = mProfits[begin]; int maxProfit = currentProfit; int[] currentResult = {0,0}; for (int i = begin; i <= end; i++) { currentResult = getMaxProfitByIndex(i ,begin, end); currentProfit = currentResult[0]; i = currentResult[1]; if(currentProfit > maxProfit) { maxProfit = currentProfit; } } return maxProfit; }private int[] getMaxProfitByIndex(int index, int begin, int end) { int currentProfits = mProfits[index]; int maxProfits = currentProfits; int[] result = {0,0}; int lastProfits = currentProfits; boolean isEnd = false; int currentProfit; int currentIndex; result[0] = currentProfits; result[1] = index; if (currentProfits > 0) { for (int len = 1; len < N; len++) { if (index != begin && len == (N-1)) { continue; } currentIndex = getIndex(index, len); currentProfit = mProfits[currentIndex]; currentProfits = lastProfits + currentProfit; lastProfits = currentProfits; if(currentProfits > maxProfits) { maxProfits = currentProfits; }if(currentProfit < 0 && !isEnd && currentIndex > index && currentIndex <= end) { result[1] = currentIndex; isEnd = true; } } if (!isEnd) { result[1] = end; } result[0] = maxProfits; } return result; }private int getIndex(int index, int length) { int tempIndex = index + length; if (tempIndex <= N) { return tempIndex; } else { return tempIndex - N; } }private class TaskWithResult implements Callable { private int begin; private int end; public TaskWithResult(int tempBegin, int tempEnd) { begin = tempBegin; end = tempEnd; }@Override public Integer call() throws Exception { return getProfitFromBeginToEnd(begin, end); } } }

【算法|【算法】求一个数组中连续数字之和最大的值】需要继续考虑下是否还有更好的算法。