CareerCup

If you already know how to solve max subsequence problem, you already know a O(n) solution for this problem too
1. In the first iteration find the subsequence that has maximum sum
2. change sign of all the elements in the array
3. Now, find the maximum sum subsequence again

The absolute maximum should now be either of the sub-sequences computed from 1&3.
To be optimal, 2&3 can be combined.

Kadane’s Algorithm:

Initialize:
max_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

If we are just comparing the min and max subsequence, how would 398 come then??

int maxsequence(int a[], int size)
{
int current_max = 0;
int real_max = current_max;
for(i=0; i<size; i++)
{
current_max += a[i];
if(current_max <= 0)
current_max = 0;
else if(current_max > real_max)
real_max = current_max;
}
return real_max;
}

Find max subsequence and min subsequence in one loop then compare the absolute value of max subsequence and min subsequence

I guess the question wants a subarray rather than a subsequence .

Reasoning: Example 100,-2,300
In this case if we take the maximum subsequence it shall be just 100,300 which sums to 400
But the answer mentioned is 398 .

#include<iostream>
using namespace std;



int max_subarray(int a[],int n)
{
int i;
int sum_here=0;
int sum=0;
for(i=0;i<n;i++)
{
sum_here+=a[i];
if(sum_here<0)
sum_here=0;
if(sum_here>sum)
sum=sum_here;
}
return sum;
}

int main()
{
int i,n;
cin>>n;
int a[n];
for(i=0;i<n;i++)
cin>>a[i];
int a1,a2,max;
a1=max_subarray(a,n);
for(i=0;i<n;i++)
a[i]=-a[i];
a2=max_subarray(a,n);
max=a1>a2?a1:a2;
cout<<"\n"<<max;
}

#include<stdio.h>
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int s[9],i,k,start;
int a[9]={0,-2,-3,4,-1,-2,1,5,-3};
s[0]=0;
for(i=1;i<9;i++)
{
s[i]=max(s[i-1]+a[i],a[i]);
if(s[i]==a[i])
start=i;
}
k=i-1;
printf("%d",s[k]);
return 0;
}
~

Kadane’s Algorithm, including sum for negative numbers:

public static void main(String[] args) {

		int[] arr = { 1, 2, -3, -4, 5, -2, -4 };
		int maxPositiveSum = 0;
		int maxPositiveStart = 0;
		int maxPositiveEnd = 0;
		int currentPositiveStart = 0;
		int currentPositiveSum = 0;

		int maxNegativeSum = 0;
		int maxNegativeStart = 0;
		int maxNegativeEnd = 0;
		int currentNegativeStart = 0;
		int currentNegativeSum = 0;

		for (int i = 0; i < arr.length; i++) {
			currentPositiveSum += arr[i];
			currentNegativeSum += arr[i];
			if (currentPositiveSum < 0) {
				currentPositiveSum = 0;
				currentPositiveStart = i + 1;
			} else if (currentPositiveSum > maxPositiveSum) {
				maxPositiveSum = currentPositiveSum;
				maxPositiveStart = currentPositiveStart;
				maxPositiveEnd = i;
			}
			if (currentNegativeSum > 0) {
				currentNegativeSum = 0;
				currentNegativeStart = i + 1;
			} else if (Math.abs(currentNegativeSum) > maxNegativeSum) {
				maxNegativeSum = Math.abs(currentNegativeSum);
				maxNegativeStart = currentNegativeStart;
				maxNegativeEnd = i;
			}
		}
		if (Math.abs(maxNegativeSum) > maxPositiveSum) {
			System.out.println("Start: " + maxNegativeStart + ", Emd: " + maxNegativeEnd + ", Sum: "
					+ Math.abs(maxNegativeSum));
		} else {
			System.out.println("Start: " + maxPositiveStart + ", Emd: " + maxPositiveEnd + ", Sum: " + maxPositiveSum);
		}
	}

int maxs(int a[],int n)
{
	int sum=a[0],max=a[0],prev=a[0];
	for(int i=1;i<n;i++)
	{
		sum=sum+a[i];
		if (( prev < 0&& sum > 0 ) || ( prev > 0 && sum < 0 ))
		{
			sum=a[i];
			
		}
		if(max<abs(sum))
		{
			max=sum;
		}
		prev=sum;
		
	}
	return (abs(max));
}