# Maximum sum sub-array

Here is a slightly more complicated one:

Q. Given an integer array containing N positive and negative numbers, find the sub-array having the largest sum in linear time O(N) using constant space O(1).

Want some hint?

` You need to keep track of both the maximum sum so far and the maximum sum for including an element. `

My solution (in Java):

```    int[] largestSum(int... a) {
int start = 0, end = -1, curstart = 0, last = 0, sum = Integer.MIN_VALUE;

for (int i = 0;i < a.length; i++) {
last += a[i];
sum = Math.max(last, sum);

if (sum == last) {
start = curstart;
end = i;
}
if (last < 0) {
last = 0;
curstart = i + 1;
}
}
return Arrays.copyOfRange(a, start, end + 1);
}
```

# Multiplies all except itself

That’s another simple algorithmic challenge.

Q. Given an array of integers A of size N > 1, produce an output array B of size N with B[i] = A*A…*A[i – 1]*A[i + 1]…*A[N], that is multiplies all elements in A except A[i] itself. Do it in linear time O(N) without using division.

Please think about it first before looking at my answer and I hope there is a better one than mine.

My solution (written in Java):

```void mul(int[] a, int[] b) {
// Compute b[i] = aa...a[i]
b = a;
for (int i = 1; i < a.length; i++) {
b[i] = b[i - 1] * a[i];
}
// Compute result, with v = a[n - 1]a[n - 2]...a[i] after loop i
int v = 1;
for (int i = a.length - 1; i > 0; i--) {
b[i] = b[i - 1] * v;
v *= a[i];
}
b = v;
}
```

# Detect duplicates

Trying to start a new category to archive some algorithmic problems that I come across. Let’s start with a very simple one.

Q. Given an array of N elements in which each element is an integer between 1 and N, detect if there are any duplicates in linear time O(n) and constant space O(1).

My solution (in Java):

```// If we are allowed to modify the array, it can be as simple as the following.
boolean detectDup(int[] a) {
for (int i = 0; i < a.length; i++) {
int d = Math.abs(a[i]) - 1;
if (a[d] < 0) {
return true;
}
a[d] = -a[d];
}
return false;
}
```