LIS & Kadane's algorithm

Overview

Two array problems share one idea: define dp[i] as the best answer that ends exactly at index i, then combine or restart at each step. Kadane's algorithm finds the maximum contiguous subarray sum by asking, at every element, whether extending the running sum beats starting fresh. Longest increasing subsequence asks, for each element, which earlier smaller element gives the longest chain to extend. The "ending at i" framing is what makes both tractable — and the global answer is then the best over all i, not simply the last entry.

Why it matters

Kadane's is the standard way to find the best window in a stream of gains and losses — peak trading intervals, best signal segment, most profitable period — in a single pass. LIS underlies patience sorting, version-compatibility chains, and any "longest chain of improving measurements" query. Both are also common interview problems precisely because the "ending at i" insight is not obvious from the brute force.

Core concepts

Kadane's recurrence. cur = max(a[i], cur + a[i]) — either the best subarray ending here starts at i, or it extends the previous one. Track best = max(best, cur) as you go.

Initialise from a[0], not 0. Seeding best = 0 reports 0 for an all-negative array, when the correct answer is the least-negative element. This is the classic Kadane bug, and the reason the implementation starts best = cur = a[0] and loops from index 1.

LIS recurrence. dp[i] = 1 + max(dp[j]) over all j < i with a[j] < a[i], defaulting to 1 (the element alone). O(n^2).

The answer is a maximum, not the last cell. For LIS the longest chain may end anywhere, so the result is the max over all dp[i] — returning dp[n-1] is wrong.

Strict vs non-strict. a[j] < a[i] gives strictly increasing; <= allows equal values and yields a different (non-decreasing) answer. Decide which the problem means.

Faster LIS. An O(n log n) variant keeps the smallest possible tail for each length and binary-searches it. Learn the O(n^2) form first — it is the reference you validate the clever one against.

Syntax notes

/* maximum contiguous subarray sum - O(n), one pass */
long long kadane(const int *a, int n) {
    long long best = a[0], cur = a[0];        /* seed from a[0], NOT 0 */
    for (int i = 1; i < n; i++) {
        long long ext = cur + a[i];
        cur = (a[i] > ext) ? a[i] : ext;      /* restart vs extend */
        if (cur > best) best = cur;
    }
    return best;
}

/* longest strictly increasing subsequence - O(n^2) */
int lis(const int *a, int n) {
    if (n <= 0) return 0;
    int *dp = malloc((size_t)n * sizeof *dp);
    if (!dp) return -1;
    int best = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
        if (dp[i] > best) best = dp[i];       /* answer is the MAX over all i */
    }
    free(dp);
    return best;
}

Key points:

• Kadane seeds from a[0]; guard n <= 0 before touching it.
• LIS answers with the maximum over all dp[i].
• long long for the sum — 32-bit sums overflow on large arrays.

Lesson

Two 1-D array DPs: the longest increasing subsequence (dp[i] = best chain ending at i) and Kadane's maximum subarray (running best contiguous sum). Both compute a per-index answer that extends earlier ones.

Code examples

#include <stdio.h>
#include <stdlib.h>
static int lis(const int*a,int n){if(n<=0)return 0;int*dp=malloc(n*sizeof(int));int best=1;for(int i=0;i<n;i++){dp[i]=1;for(int j=0;j<i;j++)if(a[j]<a[i]&&dp[j]+1>dp[i])dp[i]=dp[j]+1;if(dp[i]>best)best=dp[i];}free(dp);return best;}
static long long kadane(const int*a,int n){long long best=a[0],cur=a[0];for(int i=1;i<n;i++){long long e=cur+a[i];cur=a[i]>e?a[i]:e;if(cur>best)best=cur;}return best;}
int main(void){
    int a[]={10,9,2,5,3,7,101,18};
    printf("longest increasing subsequence length = %d\n", lis(a,8));
    int b[]={-2,1,-3,4,-1,2,1,-5,4};
    printf("max contiguous subarray sum = %lld\n", kadane(b,9));
    return 0;
}

Line by line

Common mistakes

Requiring contiguity for LIS; resetting Kadane's sum to 0 on all-negative input.

Debugging tips

Compiler errors and warnings:

• -Wsign-compare between int i and a size_t length; keep the index int.
• No warning for the best = 0 seed bug — only an all-negative test catches it.

Runtime symptoms:

• Kadane returns 0 for an all-negative array. You seeded best = 0. Seed from a[0].
• Crash on an empty array. a[0] was read without a n <= 0 guard.
• LIS returns 1 for a clearly increasing array. The comparison is backwards (a[j] > a[i]), or you compared dp values instead of array values.
• LIS is off by one at the end. You returned dp[n-1] instead of the maximum over all dp[i].
• Sums are wrong for large inputs. int overflow — accumulate in long long.

Technique: test both with three inputs: an all-positive array, an all-negative array, and a single element. Those three catch nearly every seeding and boundary bug.

Memory safety

• Read of a[0] before validating n. Kadane's seed dereferences the first element; a zero-length array makes that an out-of-bounds read. Guard n <= 0 first and decide what an empty input should return.
• LIS allocation. malloc(n * sizeof *dp) — validate n > 0, cast to size_t, and check for NULL.
• malloc vs calloc. The LIS table is fully written (dp[i] = 1) before it is read, so malloc is correct here; had the inner loop read dp[i] first, it would be reading garbage.
• Signed overflow. Summing int values into an int is undefined on overflow. Use long long, and consider the range of the input.
• Free on every path, including the early n <= 0 return.

Real-world uses

Concrete uses: Kadane's finds the most profitable contiguous period in a series of daily gains and losses, the strongest segment of a signal, or the best-scoring region in a genome scan. LIS appears in patience sorting, in computing the longest chain of compatible versions or events, and as a subroutine in diff-like tools. Both are single-pass or near-single-pass, which matters for streaming data.

Professional best practices:

Beginner:

• Always test the all-negative case for Kadane's.
• State whether LIS should be strict or non-decreasing and encode it in the comparison.

Intermediate:

• Track the start and end indices alongside the sum when the caller needs the actual window, not just its total.
• Use the O(n log n) LIS for large inputs, validated against the O(n^2) reference.
• Choose the accumulator width from the data range — a million elements of magnitude 10^6 overflows 32 bits comfortably.

Practice tasks

1. (Beginner) Kadane's sum. Implement long long kadane(const int *a, int n). Requirements: correct for all-negative input; guard n <= 0. Example: {-2,1,-3,4,-1,2,1,-5,4} -> 6; {-3,-1,-2} -> -1. Concepts: extend-or-restart, seeding.

2. (Beginner) LIS length. Implement the O(n^2) int lis(const int *a, int n). Example: {10,9,2,5,3,7,101,18} -> 4. Concepts: best-ending-at-i, max over all i.

3. (Intermediate) Report the window. Extend Kadane's to also return the start and end indices of the best subarray. Hint: record a candidate start whenever you restart. Concepts: tracking provenance in a DP.

4. (Intermediate) Strict vs non-strict. Produce both LIS variants and show an input where they differ. Example: {1,2,2,3} -> 3 strict, 4 non-decreasing. Concepts: specifying the comparison precisely.

Summary

Both problems come from defining dp[i] as the best answer ending at index i. Kadane's asks at each element whether to extend the running sum or restart from that element, seeding from a[0] so an all-negative array returns its least-negative element rather than 0. LIS takes the longest chain among earlier smaller elements and adds one, defaulting to 1 — and the answer is the maximum over all dp[i], never just the last entry. Guard the empty input before reading a[0], accumulate sums in long long, and be explicit about whether "increasing" is strict.

Practice with these exercises

• Longest increasing subsequence
• Maximum subarray (Kadane)