'finding the start and end index for a max sub array
public static void main(String[] args) {
int arr[]= {0,-1,2,-3,5,9,-5,10};
int max_ending_here=0;
int max_so_far=0;
int start =0;
int end=0;
for(int i=0;i< arr.length;i++)
{
max_ending_here=max_ending_here+arr[i];
if(max_ending_here<0)
{
max_ending_here=0;
}
if(max_so_far<max_ending_here){
max_so_far=max_ending_here;
}
}
System.out.println(max_so_far);
}
}
this program generates the max sum of sub array ..in this case its 19,using {5,9,-5,10}.. now i have to find the start and end index of this sub array ..how do i do that ??
Solution 1:[1]
This is a C program to solve this problem. I think logic is same for all languages so I posted this answer.
void findMaxSubArrayIndex(){
int n,*a;
int start=0,end=0,curr_max=0,prev_max=0,start_o=0,i;
scanf("%d",&n);
a = (int*)malloc(sizeof(int)*n);
for(i=0; i<n; i++) scanf("%d",a+i);
prev_max = a[0];
for(i=0; i<n; i++){
curr_max += a[i];
if(curr_max < 0){
start = i+1;
curr_max = 0;
}
else if(curr_max > prev_max){
end = i;
start_o = start;
prev_max = curr_max;
}
}
printf("%d %d \n",start_o,end);
}
Solution 2:[2]
Fixing Carl Saldanha solution:
int max_ending_here = 0;
int max_so_far = 0;
int _start = 0;
int start = 0;
int end = -1;
for(int i=0; i<array.length; i++) {
max_ending_here = max_ending_here + array[i];
if (max_ending_here < 0) {
max_ending_here = 0;
_start = i+1;
}
if (max_ending_here > max_so_far) {
max_so_far = max_ending_here;
start = _start;
end = i;
}
}
Solution 3:[3]
Here is algorithm for maxsubarray:
public class MaxSubArray {
public static void main(String[] args) {
int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 };
//int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
//int[] intArr={-6,-2,-3,-4,-1,-5,-5};
findMaxSubArray(intArr);
}
public static void findMaxSubArray(int[] inputArray){
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = Integer.MIN_VALUE;
int cumulativeSum= 0;
int maxStartIndexUntilNow=0;
for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
int eachArrayItem = inputArray[currentIndex];
cumulativeSum+=eachArrayItem;
if(cumulativeSum>maxSum){
maxSum = cumulativeSum;
maxStartIndex=maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
if (cumulativeSum<0){
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}
}
System.out.println("Max sum : "+maxSum);
System.out.println("Max start index : "+maxStartIndex);
System.out.println("Max end index : "+maxEndIndex);
}
}
Solution 4:[4]
Here is a solution in python - Kadane's algorithm extended to print the start/end indexes
def max_subarray(array):
max_so_far = max_ending_here = array[0]
start_index = 0
end_index = 0
for i in range(1, len(array) -1):
temp_start_index = temp_end_index = None
if array[i] > (max_ending_here + array[i]):
temp_start_index = temp_end_index = i
max_ending_here = array[i]
else:
temp_end_index = i
max_ending_here = max_ending_here + array[i]
if max_so_far < max_ending_here:
max_so_far = max_ending_here
if temp_start_index != None:
start_index = temp_start_index
end_index = i
print max_so_far, start_index, end_index
if __name__ == "__main__":
array = [-2, 1, -3, 4, -1, 2, 1, 8, -5, 4]
max_subarray(array)
Solution 5:[5]
The question is somewhat unclear but I'm guessing a "sub-array" is half the arr object.
A lame way to do this like this
public int sum(int[] arr){
int total = 0;
for(int index : arr){
total += index;
}
return total;
}
public void foo(){
int arr[] = {0,-1,2,-3,5,9,-5,10};
int subArr1[] = new int[(arr.length/2)];
int subArr2[] = new int[(arr.length/2)];
for(int i = 0; i < arr.length/2; i++){
// Lazy hack, might want to double check this...
subArr1[i] = arr[i];
subArr2[i] = arr[((arr.length -1) -i)];
}
int sumArr1 = sum(subArr1);
int sumArr2 = sum(subArr2);
}
I image this might not work if the arr contains an odd number of elements.
If you want access to a higher level of support convert the primvate arrays to a List object
List<Integer> list = Arrays.asList(arr);
This way you have access to a collection object functionality.
Also if you have the time, take a look at the higher order functional called reduce. You will need a library that supports functional programming. Guava or lambdaJ might have a reduce method. I know that apache-commons lacks one, unless you want to hack to together it.
Solution 6:[6]
The only thing I have to add (to several solutions posted here) is to cover the case that all the integers are negative, in which case the max sub array will be just the max element. Pretty easy to do that.. just have to track max element and index of the index of the max element as you iterate through it. If the max element is negative, return it's index instead.
There is also the case of overflow to possibly handle. I've seen algorithm tests that take than into account.. IE, suppose MAXINT was one of the elements and you tried to add to it. I believe some of the Codility (coding interview screeners) tests take that into account.
Solution 7:[7]
In python solving 3 problem i.e., sum, array elements and index.
def max_sum_subarray(arr):
current_sum = arr[0]
max_sum = arr[0]
curr_array = [arr[0]]
final_array=[]
s = 0
start = 0
e = 0
end = 0
for i in range(1,len(arr)):
element = arr[i]
if current_sum+element > element:
curr_array.append(element)
current_sum = current_sum+element
e += 1
else:
curr_array = [element]
current_sum = element
s = i
if current_sum > max_sum:
final_array = curr_array[:]
start = s
end = e
max_sum = current_sum
print("Original given array is : ", arr)
print("The array elements that are included in the sum are : ",final_array)
print("The starting and ending index are {} and {} respectively.".format(start, end))
print("The maximum sum is : ", max_sum)
# Driver code
arr = [-12, 15, -13, 14, -1, 2, 1, -5, 4]
max_sum_subarray(arr)
- By Om Prasad Nayak
Solution 8:[8]
public static void maxSubArray(int []arr){
int sum=0,j=0;
int temp[] = new int[arr.length];
for(int i=0;i<arr.length;i++,j++){
sum = sum + arr[i];
if(sum <= 0){
sum =0;
temp[j] = -1;
}else{
temp[j] = i;
}
}
rollback(temp,arr);
}
public static void rollback(int [] temp , int[] arr){
int s =0,start=0 ;
int maxTillNow = 0,count =0;
String str1 = "",str2="";
System.out.println("============");
// find the continuos index
for(int i=0;i<temp.length;i++){
if(temp[i] != -1){
s += arr[temp[i]];
if(s > maxTillNow){
if(count == 0){
str1 = "" + start;
}
count++;
maxTillNow = s;
str2 = " " + temp[i];
}
}else{
s=0;
count =0;
if(i != temp.length-1)
start = temp[i+1];
}
}
System.out.println("Max sum will be ==== >> " + maxTillNow);
System.out.print("start from ---> "+str1 + " end to --- >> " +str2);
}
Solution 9:[9]
public void MaxSubArray(int[] arr)
{
int MaxSoFar = 0;
int CurrentMax = 0;
int ActualStart=0,TempStart=0,End = 0;
for(int i =0 ; i<arr.Length;i++)
{
CurrentMax += arr[i];
if(CurrentMax<0)
{
CurrentMax = 0;
TempStart = i + 1;
}
if(MaxSoFar<CurrentMax)
{
MaxSoFar = CurrentMax;
ActualStart = TempStart;
End = i;
}
}
Console.WriteLine(ActualStart.ToString()+End.ToString());
}
Solution 10:[10]
An O(n) solution in C would be :-
void maxsumindex(int arr[], int len)
{
int maxsum = INT_MIN, cur_sum = 0, start=0, end=0, max = INT_MIN, maxp = -1, flag = 0;
for(int i=0;i<len;i++)
{
if(max < arr[i]){
max = arr[i];
maxp = i;
}
cur_sum += arr[i];
if(cur_sum < 0)
{
cur_sum = 0;
start = i+1;
}
else flag = 1;
if(maxsum < cur_sum)
{
maxsum = cur_sum;
end = i;
}
}
//This is the case when all elements are negative
if(flag == 0)
{
printf("Max sum subarray = {%d}\n",arr[maxp]);
return;
}
printf("Max sum subarray = {");
for(int i=start;i<=end;i++)
printf("%d ",arr[i]);
printf("}\n");
}
Solution 11:[11]
Here is a solution in Go using Kadane's Algorithm
func maxSubArr(A []int) (int, int, int) {
start, currStart, end, maxSum := 0, 0, 0, A[0]
maxAtI := A[0]
for i := 1; i < len(A); i++ {
if maxAtI > 0 {
maxAtI += A[i]
} else {
maxAtI = A[i]
currStart = i
}
if maxAtI > maxSum {
maxSum = maxAtI
start = currStart
end = i
}
}
return start, end, maxSum
}
Solution 12:[12]
Here is a C++ solution.
void maxSubArraySum(int *a, int size) {
int local_max = a[0];
int global_max = a[0];
int sum_so_far = a[0];
int start = 0, end = 0;
int tmp_start = 0;
for (int i = 1; i < size; i++) {
sum_so_far = a[i] + local_max;
if (sum_so_far > a[i]) {
local_max = sum_so_far;
} else {
tmp_start = i;
local_max = a[i];
}
if (global_max < local_max) {
global_max = local_max;
start = tmp_start;
end = i;
}
}
cout<<"Start Index: "<<start<<endl;
cout<<"End Index: "<<end<<endl;
cout<<"Maximum Sum: "<<global_max<<endl;
}
int main() {
int arr[] = {4, -3, -2, 2, 3, 1, -2, -3, 4,2, -6, -3, -1, 3, 1, 2};
maxSubArraySum(arr, sizeof(arr)/sizeof(arr[0]));
return 0;
}
Solution 13:[13]
pair<int,int> maxSumPair(vector<int> arr) {
int n = arr.size();`
int currSum = arr[0], maxSoFar = arr[0];
int start = 0, end ,prev = currSum;
unordered_map<int,pair<int,int>> mp;
for(int i = 1 ; i < n ; i++) {
prev = currSum;
if(currSum == arr[i]) {
end = i-1;
mp.insert({currSum,{start,end}});
start = i;
}
if(maxSoFar < currSum) {
maxSoFar = currSum;
end = i;
mp.insert({currSum,{start,end}});
}
}
int maxSum = INT_MIN;
for(auto it: mp) {
if(it.first > maxSum) {
maxSum = it.first;
}
}
return mp[maxSum];
}
Solution 14:[14]
int maxSubarraySum(int arr[], int n){
int max_so_far = -1 * Integer.MAX_VALUE;
int max_curr = 0;
int start = 0;
int end = 0;
for(int i=0; i < arr.length; i++){
max_curr = max_curr + arr[i];
if(max_so_far < max_curr){
max_so_far = max_curr;
}
if( max_curr < 0){
max_curr = 0;
start = i+1;
}
else
end = i;
}
start = end < start ? end : start;
System.out.println( start + "..." + end);
return max_so_far;
}
Solution 15:[15]
Maximum sub array in golang implementation
package main
import (
"fmt"
)
func main() {
in := []int{-2, -12, 23, -10, 11, -6, -1}
a, b := max(in)
fmt.Println(a)
fmt.Println(b)
}
func max(in []int) ([]int, int) {
var p, r, sum, sf, psf int
if len(in) == 0 {
return in, 0
}
sum = in[0]
for i, n := range in {
sf += n
if sf > sum {
sum = sf
p = psf
r = i
}
if sf <= 0 {
psf = i + 1
sf = 0
}
}
return in[p : r+1], sum
}
Solution 16:[16]
I think this will help to get the start and end index
// Time Complexity = O(N)
// Space Complexity = O(1)
public static int maxSum2(int[] nums){
int globalSum = Integer.MIN_VALUE;
int currentSum = 0;
int start=0;
int end=0;
for(int i=0; i<nums.length;i++){
currentSum += nums[i];
if (currentSum>globalSum){
globalSum = currentSum;
end = i;
}
if (currentSum<0){
currentSum=0;
start = i+1;
}
}
System.out.println(start + " " + end);
return globalSum;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow